Merge Sort merge Sort + diagram + recursive / non-recursive

The main idea of (merge sort) is: to merge gradually several ordered sequences, and finally merge them into one ordered sequence
Two-way merge sort(2-way merge sort) is the simplest sorting method in merge sort

(1)Recursive implementation of two-way merge sort

// Recursive implementation of two-way merge sort
void merge(vector<int> & amp; arr,int left, int mid, int right) {
int n = right - left + 1;
vector<int> help(n, 0);
int i = 0,a = left, b = mid + 1;
while (a <= mid & amp; & amp; b <= right) {
help[i + + ] = arr[a] <= arr[b] ? arr[a + + ] : arr[b + + ];
}
while (a <= mid) { // Finish the first subsequence
help[i + + ] = arr[a + + ];
}
while (b <= right) { // Finishing work on the second subsequence
help[i + + ] = arr[b + + ];
}
for (int i = 0; i < n; i + + ) {
arr[i + left] = help[i];
}
}

void mergeSort(vector<int> & amp; arr,int left, int right) {
if (left == right) return; // There is only 1 record, the recursion ends
int mid = (left + right) / 2;
//int mid = left + ((right - left) >> 1);
mergeSort(arr,left, mid);//Merge and sort the first half of the subsequence
mergeSort(arr,mid + 1, right);//The second half of the subsequence after merge sorting
merge(arr,left, mid, right);//Merge two sorted subsequences
}

Two-way merge sort requires $\left \lceil log2^{n} \right \rceil$ Time, the time performance of merging two subsequences is $O(n)$ . Therefore, the time complexity of two-way merge sort is $O(nlog2^{n})$ , which is the best, worst, and average time performance of the merge sort algorithm.

Two-way merge sort During the merging process, the same amount of storage space is required as the sequence to be sorted, and the space complexity is $O(n)$ . Two-way merge sort is astable sorting method.

Summary: The recursive implementation of merge sort is a top-down method, which is simple in form but relatively inefficient.

(2) Non-recursive implementation of two-way merge sort

Analyze the recursive execution process of Two-way merge sort. As shown in the figure, the sequence to be sorted with n records can be regarded as n An ordered subsequence of length 1 is then merged pairwise to obtain $\left \lceil \frac{n}{2} \right \rceil$ A length of 2 Ordered subsequences (the length of the last ordered sequence may be 1), and then perform pairwise merging to obtain $\left \lceil \frac{n}{4} \right \rceil$ A length of 4 Ordered subsequences (the length of the last ordered sequence may be less than 4), and so on until an ordered sequence of length n is obtained.

The key issues that need to be solved in the non-recursive implementation of two-way merge sort are:

① How to construct the initial ordered subsequence?
② How to merge ordered subsequences in pairs to complete a merge?
③ How to control the end of the two-way merge?

Solution to Problem ①: Assume that the sequence to be sorted contains n records, then the entire sequence can be regarded as n with a length of 1. subsequence

Solution to Problem ②: In a merge, except for the last ordered sequence, the number of records in other ordered sequences (called sequence length) is the same, use h strong>representation. The current task is to merge several adjacent ordered sequences of length h and the last ordered sequence whose length may be less than h , store the result in help[n]. For this purpose, set parameter i to point to the first record of the sequence to be merged. Initially i = 0, obviously the step size of the merge should be 2h. During the merging process, there are three situations:

Case 1: If i + 2h <= n, it means that the lengths of two adjacent ordered subsequences to be merged are both < strong>h , as shown in the figure below: perform a merge, and after completion, add 2h to prepare for the next merge.

Case 2: If i + h < n, it means that there are still two adjacent ordered subsequences, one with a length of h, the other length is smaller than h, as shown in the figure below: execute the merge of these two ordered sequences, and exit the merge after completion

Case 3: If i + h >= n, it means that only the next ordered subsequence is left, As shown in the figure below, No need to merge

To sum up, the member function of one-pass merge sort is defined as follows:

void mergePass(vector<int> & amp; arr,int h,int n) {
int i = 0;
while (i + 2 * h <= n) { // There are two subsequences of length h
merge(arr,i, i + h - 1, i + 2 * h - 1);
i = i + 2 * h;
}
if (i + h < n) { // One of the two subsequences has a length less than h
merge(arr,i, i + h - 1, n - 1);
}
}

Solution to Problem ③: At the beginning, the length of the ordered subsequence is 1, and at the end, the length of the ordered subsequence is n. Therefore, the length of the ordered subsequence can be used to control the end of the sorting process. The member function of the two-way merge sortnon-recursive algorithm is defined as follows:

void mergeSort2(vector<int> & amp; arr,int n) {
int h = 1;
while (h < n) { // One of the two subsequences has a length less than h
mergePass(arr,h, n); // One pass merge sort
h = 2 * h;
}
}

Summary: The non-recursive implementation of merge sort is a bottom-up method. The algorithm is more efficient, but the algorithm is more complex.

(3) C++ complete code:

/*
The main idea of merge sort is to gradually merge several ordered sequences into one ordered sequence.
2-way merge sort is the simplest sorting method in merge sort

we
*/
#include 
#include 
using namespace std;

// Recursive implementation of two-way merge sort
void merge(vector<int> & amp; arr,int left, int mid, int right) {
int n = right - left + 1;
vector<int> help(n, 0);
int i = 0,a = left, b = mid + 1;
while (a <= mid & amp; & amp; b <= right) {
help[i + + ] = arr[a] <= arr[b] ? arr[a + + ] : arr[b + + ];
}
while (a <= mid) { // Finish the first subsequence
help[i + + ] = arr[a + + ];
}
while (b <= right) { // Finishing work on the second subsequence
help[i + + ] = arr[b + + ];
}
for (int i = 0; i < n; i + + ) {
arr[i + left] = help[i];
}
}

void mergeSort(vector<int> & amp; arr,int left, int right) {
if (left == right) return; // There is only 1 record, the recursion ends
int mid = (left + right) / 2;
//int mid = left + ((right - left) >> 1);
mergeSort(arr,left, mid);//Merge and sort the first half of the subsequence
mergeSort(arr,mid + 1, right);//The second half of the subsequence after merge sorting
merge(arr,left, mid, right);//Merge two sorted subsequences
}

void mergePass(vector<int> & amp; arr,int h,int n) {
int i = 0;
while (i + 2 * h <= n) { // There are two subsequences of length h
merge(arr,i, i + h - 1, i + 2 * h - 1);
i = i + 2 * h;
}
if (i + h < n) { // One of the two subsequences has a length less than h
merge(arr,i, i + h - 1, n - 1);
}
}

void mergeSort2(vector<int> & amp; arr,int n) {
int h = 1;
while (h < n) { // One of the two subsequences has a length less than h
mergePass(arr,h, n); // One pass merge sort
h = 2 * h;
}
}
int main() {
vector arr = { 6,4,2,3,9,1,4 };
int n = arr.size();
//mergeSort(arr, 0, n - 1);
mergeSort2(arr,n);
for (int i = 0; i < n; i + + ) {
cout << " " << arr[i] << " " << endl;
}
system("pause");
return 0;
}

Reference books for this article: Data Structure-From Concept to C++ Implementation (Third Edition) edited by Wang Hongmei, Wang Hui, and Wang Xinxin

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57518 people are learning the system