Merge sort implementation code and ideas

First consider how to combine two ordered sequences. This is very simple, just compare the first number of two sequences, pick the one who is smaller, and then delete the number in the corresponding sequence. Then compare, if several columns are empty, then simply pull out the data of another sequence.

View Code 
 //Merge the ordered arrays a[] and b[] into c[]
 void MemeryArray(int a[], int n, int b[], int m, int c[])
 {
     int i, j, k;

     i = j = k = 0;
     while (i < n && j < m)
     {
         if (a[i] < b[j])
             c[k++] = a[i++];
         else
             c[k++] = b[j++]; 
     }

     while (i < n)
         c[k++] = a[i++];

     while (j < m)
         c[k++] = b[j++];
 }

It can be seen that the efficiency of merging ordered sequence is relatively high, which can reach O(n).

After solving the above problem of merging ordered sequence, the basic idea of merge sort is to divide the array into two groups A and B. If the data in these two groups are in order, it is very convenient to sort the two groups of data. How to make the data in these two groups orderly?

You can divide groups A and B into two groups. By analogy, when the separated group has only one data, it can be considered that the group has reached the order, and then merge the two adjacent groups. So you do merge sort by recursively breaking up the sequence and then merging the sequence.

View Code 
 //There will be two ordered sequences a[first...mid] and a[mid...last].
 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);    //On the left in order
         mergesort(a, mid + 1, last, temp); //The right order
         mergearray(a, first, mid, last, temp); //Combine 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;
 }

The efficiency of merge sort is relatively high. Let the length of the sequence be N, and divide the sequence into small sequences in a total of logN steps. Each step is a process of merging ordered sequence, and the time complexity can be recorded as O(N), so the total is O(N*logN). Since merge sort operates on adjacent data each time, several sorting methods (quicksort, merge sort, hill sort, heap sort) of merge sort at O (N * logN) are also efficient