C++ implementation of merge sort algorithm

The example of this paper describes the merge sort algorithm implemented by C++. I will share it with you for your reference as follows:

Merge sort

Merge sort (MERGE-SORT) is an effective sorting algorithm based on merge operation.
This algorithm is a very typical application of divide and conquer (Divide and Conquer). Combine the ordered subsequence to get a completely ordered sequence.
That is, make each subsequence in order first, and then make the subsequence between segments in order. If two ordered tables are merged into one ordered table, it is called two-way merge.

The merge process

1. Compare the sizes of a[i] and a[j]. If a[i]≤a[j], copy the element a[i] from the first ordered table into temp[k], and add 1 to i and k, respectively;
2. Otherwise, copy a[j] from the second ordered table into temp[k] and add 1 to j and k, respectively.
3. Repeat the cycle until one of the ordered tables has been fetched, and then copy the remaining elements from the other ordered table into the unit in r from subscript k to subscript t.

We usually use recursion to realize the algorithm of merge sort. We first sort the interval to be sorted [first, last] at the midpoint 2, then sort the left subinterval, then sort the right subinterval, and finally merge the left and right intervals into an ordered interval [first,last] with one merge operation.

How merge works

Step 1: request a space whose size is the sum of two sorted sequences. This space is used to store the merged sequences
Step 2: set two Pointers to the starting positions of the two sorted sequences
Step 3: compare the elements to which the two Pointers point, select the relatively small element to put into the merge space, and move the pointer to the next 1
Repeat step 3 until one pointer exceeds the end of the sequence and copy all the remaining elements of the other sequence directly to the end of the merged sequence.

Algorithm complexity

The time complexity is O(nlogn), which is the best, worst, and average time performance of the algorithm.
The space complexity is O(n).
The number of comparison operations is between (nlogn) / 2 and nlogn-n + 1.
The number of assignment operations is (2nlogn).
Merge sort takes up a lot of memory, but it is an efficient and stable algorithm.

Algorithm C++ code

// Merge two sequences 
void mergeArray(int arr[], int first, int mid, int last, int temp[])
{
  int i = first;
  int j = mid + 1;
  int m = mid ;
  int n = last;
  int k = 0;
  while (i <= m && j<=n)
  {
    if (arr[i] <= arr[j])
      temp[k++] = arr[i++];
    else
      temp[k++] = arr[j++];
  }
  while (i <= m)
    temp[k++] = arr[i++];
  while (j <= n)
    temp[k++] = arr[j++];
  for (i = 0; i < k; i++)
    arr[first + i] = temp[i];
}
void mySort(int arr[], int first, int last, int temp[])
{
  if (first < last)
  {
    int mid = (first + last) / 2;
    mySort(arr, first, mid, temp);
    mySort(arr, mid+1, last, temp);
    mergeArray(arr, first, mid, last, temp);
  }
}
bool mergeSort(int arr[], int len)
{
  int*p = new int[len];
  if (NULL == p)
    return false;
  mySort(arr, 0, len - 1, p);
  delete[] p;
  return true;
}

Algorithm testing

#include <iostream>
using namespace std;
// The above merge sort source code 
int main()
{
  int arr[] = { 2, 23, 32, 34, 45, 6, 5, 65, 7, 6, 87, 87, 8, 798, 34, 35, 46, 45, 65, 756, 876, 8, 7, 87, 87, 5, 34, 344, 3, 32 };
  int len = sizeof(arr) / sizeof(int);
  mergeSort(arr, len);
  for (int i = 0; i < len; i++)
    cout << arr[i] << " ";
  cout << endl;
  system("pause");
}

Operation results:

2 3 5 5 6 6 7 7 8 8 23 32 32 34 34 34 35 45 45 46 65 65 87 87 87 87 344 756 798 876
 Please press any key to continue . . .

I hope this article is helpful to you C++ programming.