Wednesday, December 19, 2018
Home > C++ > C++ Merge Sort

# C++ Merge Sort

Merge sort algorithm belongs to the divide and conquer family of algorithms. As the name suggests this family of algorithms divides the given data usually an array. This algorithm also divides the array into two halves and then calls itself again for the divided halves. This process continues until each element of the given array is separated. i.e. the size of the array becomes 1. And at the end, C++ merge sort algorithm compares each element of the array and then merges it to sort the array. Merge sort in c++ is the implementation of this algorithm.

## Pseudo Code for Merge Sort in C++ Algorithm

The pseudo code for this algorithm is

```MergeSort(My_Arr[], left,  right) If left <right
1- Find the middle point to divide the array into two halves:
middle m = (left+right)/2
2- Call mergeSort for the first half:
Calling mergeSort(My_Arr, left, middle) function.
3- Call mergeSort for the second half:
Calling  mergeSort(My_Arr, middle+1, right) function again.
4- Merge the elements of the array:
Calling the merge(My_Arr, left, middle, right) function.```

My_Arr[] is the given array which we will sort using the merge sort algorithm. left is the index of the leftmost element of the array and right is the index of the rightmost element in the array. The middle is the index from where we will divide the array.

Here is the simple graphical example of working of merge sort algorithm.

 15 90 10 101 3

left = 0

right = 5

middle = (left +right )/2  => 5/2 =>3

so we will divide the array from 3rd index.

 15 90 10 101 3

As the left index is less than right index so again calling the merge sort algorithm for each half.

 15 90 10 101 3

Since the left index is still less than the right index so we are again calling the merge sort algorithm.

 15 90 10 101 3

Now as the size of the array is equal to 1 i.e. each element of the array is separated. Now we will merge the array elements.

 15 90 10 3 101
 10 15 90 3 101
 3 10 15 90 101

After merging each element of the array we have the sorted array. In the above example, we sort the array in ascending order though we can sort the array in descending order as well.

## C++ code implementation of merge sort algorithm

### Ascending order

```#include "stdafx.h"
#include"iostream"

using namespace std;
void merge(int my_arr[], int left, int middle, int right);
void mergeSort(int my_arr[], int left, int right);
void display(int my_arr[], int size);
int main()
{
int *my_arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
my_arr = new int[size];

cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index " << i + 1 << " : ";
cin >> my_arr[i];
}
cout<<"Unsorted array is \n";
display(my_arr, size);
mergeSort(my_arr, 0, size - 1);
cout <<"\nSorted array in Descending order using merge sort.\n";
display(my_arr, size);
return 0;
}
void merge(int arr[], int left, int middle, int right)
{
int i, j, k;
int n1 = middle - left + 1;
int n2 = right - middle;
int *left_arr;
int *right_arr;
/* create temp arrays */
left_arr = new int[n1];
right_arr = new int [n2];
/* Copying data to temp arrays */
for (i = 0; i < n1; i++)
{
left_arr[i] = arr[left + i];
}
for (j = 0; j < n2; j++)
{
right_arr[j] = arr[middle + 1 + j];
}
i = 0; // first index of first half
j = 0; // first index of second 2nd
k = left; // firts index of merged array
while (i < n1 && j < n2)
{
if (left_arr[i] >= right_arr[j])
{
arr[k] = left_arr[i];
i++;
}
else
{
arr[k] = right_arr[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = left_arr[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = right_arr[j];
j++;
k++;
}
}
void mergeSort(int my_arr[], int left, int right)
{
if (left < right)
{
int m = left + (right - left) / 2;
mergeSort(my_arr, left, m);
mergeSort(my_arr, m + 1, right);
merge(my_arr, left, m, right);
}
}
void display(int my_arr[], int size)
{
int i;
for (i = 0; i < size; i++)
{
cout << my_arr[i] << "  ";
}
cout << endl;
}```

### Descending order

```#include "stdafx.h"
#include"iostream"

using namespace std;
void merge(int my_arr[], int left, int middle, int right);
void mergeSort(int my_arr[], int left, int right);
void display(int my_arr[], int size);
int main()
{
int *my_arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
my_arr = new int[size];

cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index " << i + 1 << " : ";
cin >> my_arr[i];
}
cout<<"Unsorted array is \n";
display(my_arr, size);
mergeSort(my_arr, 0, size - 1);
cout <<"\nSorted array in Ascending order using merge sort.\n";
display(my_arr, size);
return 0;
}
void merge(int arr[], int left, int middle, int right)
{
int i, j, k;
int n1 = middle - left + 1;
int n2 = right - middle;
int *left_arr;
int *right_arr;
/* create temp arrays */
left_arr = new int[n1];
right_arr = new int [n2];
/* Copying data to temp arrays */
for (i = 0; i < n1; i++)
{
left_arr[i] = arr[left + i];
}
for (j = 0; j < n2; j++)
{
right_arr[j] = arr[middle + 1 + j];
}
i = 0; // first index of first half
j = 0; // first index of second 2nd
k = left; // firts index of merged array
while (i < n1 && j < n2)
{
if (left_arr[i] <= right_arr[j])
{
arr[k] = left_arr[i];
i++;
}
else
{
arr[k] = right_arr[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = left_arr[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = right_arr[j];
j++;
k++;
}
}
void mergeSort(int my_arr[], int left, int right)
{
if (left < right)
{
int m = left + (right - left) / 2;
mergeSort(my_arr, left, m);
mergeSort(my_arr, m + 1, right);
merge(my_arr, left, m, right);
}
}
void display(int my_arr[], int size)
{
int i;
for (i = 0; i < size; i++)
{
cout << my_arr[i] << "  ";
}
cout << endl;
}```

This site uses Akismet to reduce spam. Learn how your comment data is processed.