Merge sort is an efficient sorting algorithm based on merge operations. This algorithm is a very typical application of the Divide and Conquer approach.

First consider how to merge two ordered sequences. This is very simple: just compare the first numbers of the two sequences, take the smaller one first, and delete that number from the corresponding sequence after taking it. Then compare again; if one sequence is empty, just take out the data of the other sequence one by one.

// Merge 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 merging ordered sequences is relatively efficient and can reach O(n).

After solving the above problem of merging ordered sequences, let's look at merge sort. Its basic idea is to divide the array into two groups, A and B. If the data within each group is ordered, then these two groups of data can be sorted conveniently. How can the data within these two groups be made ordered?

You can further divide groups A and B into two groups each. And so on. When a divided subgroup has only one data item, the subgroup can be considered already ordered, and then merge the two adjacent subgroups. In this way, merge sort is completed by recursively decomposing the sequence first and then merging the sequences.

// Merge 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); // Left side is ordered mergesort(a, mid + 1, last, temp); // Right side is 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; }

The efficiency of merge sort is relatively high. Let the sequence length be N. It takes a total of logN steps to divide the sequence into small sequences. Each step is a process of merging ordered sequences, and the time complexity can be recorded as O(N), so the total is O(N*logN). Because merge sort operates on adjacent data each time, among several sorting methods with O(N*logN) (quick sort, merge sort, shell sort, heap sort), merge sort is also relatively efficient.

On my computer, I compared bubble sort, direct insertion sort, merge sort, and direct use of the system's qsort() (all in Release version).

Test with 20,000 random data items:

Test with 50,000 random data items:

Then test with 200,000 random data items:

Note: Some books allocate a temporary array in mergearray() when merging ordered sequences, but too many new operations are very time-consuming. So a small change was made. Only one temporary array is allocated with new in MergeSort(). All subsequent operations share this temporary array.

Author: MoreWindows

Original: https://blog.csdn.net/morewindows/article/details/6678165