Example of C++ merge sort algorithm

Merge sort

Merge sort algorithm is a very typical application of divide and conquer. The idea of merge sort is to divide the Numbers in an array into individual Numbers; For a single number, it must be ordered, and then we combine those ordered Numbers to form an ordered sequence. That's the idea of merge sort. It's order N times logN.

Code implementation

#include <iostream>

using namespace std;

 

//There will be two ordered sequences a[first...mid] and a[mid...last]. < br / >
void mergearray(int a[], int first, int mid, int last, int temp[])

{

     int i = first, j = mid + 1;

     int m = mid,   n = last;

     int k = 0;

 

     while (i <= m && j <= n)

     {

          if (a[i] <= a[j])

               temp[k++] = a[i++];

          else

               temp[k++] = a[j++];

     }

 

     while (i <= m)

          temp[k++] = a[i++];

 

     while (j <= n)

          temp[k++] = a[j++];

 

     for (i = 0; i < k; i++)

          a[first + i] = temp[i];

}

void mergesort(int a[], int first, int last, int temp[])

{

     if (first < last)

     {

          int mid = (first + last) / 2;

          mergesort(a, first, mid, temp);    //Left ordered 

          mergesort(a, mid + 1, last, temp); //Right ordered 

          mergearray(a, first, mid, last, temp); //Then merge the two ordered sequences 

     }

}

 

bool MergeSort(int a[], int n)

{

     int *p = new int[n];

     if (p == NULL)

          return false;

     mergesort(a, 0, n - 1, p);

     delete[] p;

     return true;

}

 

int main()

{

     int arr[] = {2, 1, 4};

     MergeSort(arr, 3);

 

     for (int i = 0; i < 3; ++i)

     {

          cout<<arr[i]<<" ";

     }

     cout<<endl;

}