Data Structure: How to implement Merge Sort in C++?

Merging is the process of combining two or more sorted files into a third sorted file. Merge sort is based on the divide and conquer paradigm. It can be explained as …. Let A[p…..r] is given array with indices p = 1 to r = n. Then steps can be

          Image Source: http://en.wikipedia.org/wiki/Merge_sort 

1. Divide Step: If a given array A has zero or one element, then simply return; it is already sorted. Otherwise split A[p…..r] into two subarrays as A[p….q] and A[q+1…..r] each containing about the half of the elements.
2. Conquer Step: Conquer by recursively sorted the two sub-arrays A[p….q] and A[q+1….r]
3. Combine Step: Combine the elements back in A[p…..r] by merging the two sorted sub-arrays into the sorted sequence. Note that: the recursion bottoms out when the sub-array has just one element. So that it is trivially sorted.

Source Code:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

#include<iostream> using namespace std;   //create a class MergeSort class MergeSort{     public:         int no_of_elements;         int elements[10];     public:         void getarray();         void partition(int [] ,int ,int);         void sortit(int [], int , int, int);         void display(); };   // get the array to be sorted from the user void MergeSort::getarray(){     cout<<"How many elements?: ";     cin>>no_of_elements;     cout<<"Insert elements to sort: ";     for(int i=0;i<no_of_elements;i++){         cin>>elements[i];     } }   // recursively divide the array into sub arrays until all sub // arrays contain only one element void MergeSort::partition(int elements[], int low, int high){     int mid;     if(low<high){         mid=(low+high)/2;         // sort the left sub array         partition(elements,low,mid);           // sort the right sub array         partition(elements,mid+1,high);             sortit(elements,low,mid,high);       } } void MergeSort::sortit(int elements[], int low, int mid, int high){     int i,j,k,l,b[20];     l=low;     i=low;     j=mid+1;     while((l<=mid)&&(j<=high)){         if(elements[l]<=elements[j]){             b[i]=elements[l];             l++;         }else{             b[i]=elements[j];             j++;         }         i++;     }     if(l>mid){         for(k=j;k<=high;k++){             b[i]=elements[k];             i++;         }     }else{         for(k=l;k<=mid;k++){             b[i]=elements[k];             i++;         }     }     for(k=low;k<=high;k++){         elements[k]=b[k];     } } void MergeSort::display(){     cout<<"The sorted element is\n";     for(int i = 0 ; i < no_of_elements; i++){         cout<<elements[i]<<" ";     } } int main(){     MergeSort MS;     MS.getarray();     MS.partition(MS.elements,0,MS.no_of_elements);     MS.display();     return 0; }

Output:

How many elements? 7
Insert element to sort: 63 78 52 12 99 32 13
The sorted element is
12 13 32 52 63 78 99