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.

1590101013

left = 0

right = 5

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

so we will divide the array from 3rd index.

1590101013

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

1590101013

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

1590101013

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.

1590103101
1015903101
3101590101

 

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;
}

merge sort in c++ ascending order

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;
}

c++ merge sort descending order

Leave a Reply

Your email address will not be published. Required fields are marked *

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