1. Basic information of merge sort
1. Basic principles
Merge sort is an effective sorting algorithm based on merge operations. This algorithm is a very typical application of the divide-and-conquer method.
Merge the ordered subsequences to obtain a completely ordered sequence;
That is, order each subsequence first, and then order the subsequence segments.
Decomposition: Split the array into two arrays, and then subdivide the two arrays into 2 arrays respectively until each array finally contains one element. At this time, the single-element array is regarded as an ordered array.
Merge: Sort the divided ordered arrays, and then continue merging the previous array that divided it into an ordered array until the arrays are merged into the original arrays, which are now sorted.
2. Advantages and Disadvantages
Like selection sort, the performance of merge sort is not affected by the input data, but the performance is much better than selection sort, because the time complexity is always O(n log n). The price is additional memory space. Merge sort is an effective sorting algorithm based on merge operations. This algorithm is a very typical application using the divide-and-conquer method
3. Understanding animations
4. Complexity
1. Time complexity
Merge sort divides the collection into half groups. If the set length is n, then the number of levels to be split in half is logn, and the amount of calculation for the merge operation at each level is n. Therefore, the time complexity of merge sort is equal to the amount of operations at each level × the number of levels, that is, O(nlogn).
2. Space complexity
Merge sort requires additional space, but the additional space created by each merge will be released as the method ends, so the maximum space opened up by a single merge operation is n. Therefore, the space complexity of merge sort is O(n).
2. The idea of merging sort
Let’s first use this picture to roughly show the idea, and I will explain it in detail below.
1. The most basic operation (merging)
That is: merge the ordered subsequences to obtain a completely ordered sequence;
If there are two sorted arrays;
We’re going to merge these two arrays;1. Let’s first merge the two arrays into one array. This is very simple;
But the merged array may not be a particularly ordered array, so we have to sort it at this time;
2. We sort the two arrays and return a completely ordered sequence.
We use i to represent the first element in array A;
Use j to represent the first element in array B;
Use k to represent the new array, which is the first element of the array to be sorted;
Determine the size of i and j;
If i
Assumei
Okay, now that the principle is clarified, let’s start organizing the code ideas.
We define a merge function that accepts an array arr, as well as the left boundary left, the middle position mid and the right boundary right of the subsequence to be merged as parameters. The goal of the function is to merge the two ordered subsequences [left, mid] and [mid + 1, right] in r into the array temp.
The specific merging process is as follows:
- Define an array temp to temporarily store the ordered array.
- Define three pointers i, j and k, respectively pointing to the starting position left of the left subsequence, the starting position mid + 1 of the right subsequence, and the starting position left of the merged array temp.
- When both the i pointer and the j pointer are within the corresponding subsequence, compare the sizes of arr[i] and arr[j], and put the smaller element into temp[k]. Move the pointer i or j, and k, continue the loop comparison and fill the temp array.
- If there are remaining elements in the left subsequence, put the remaining elements into the temp array in sequence. If there are remaining elements in the right subsequence, put the remaining elements into the temp array in sequence.
- Return k to the starting position, traverse the temp array and store it in the arr array.
- Returning 0 indicates the merge process is complete.
Come on, get some code!
void merge(int arr[], int left, int mid, int right) {
int temp[100];
int i = left, j = mid + 1;
int k = left;
while (i <= mid & amp; & amp; j <= right) {
if (arr[i] < arr[j]) {
temp[k + + ] = arr[i + + ];
}
else {
temp[k + + ] = arr[j + + ];
}
}
while (i <= mid)
temp[k + + ] = arr[i + + ];
while (j <= right)
temp[k + + ] = arr[j + + ];
k = left;
while (k <= right) {
arr[k] = temp[k];
k++;
}
}
2. Divide and conquer method expands the scope of operation
Come down and start the second operation: points! ! !
When we merged above, we used ordered arrays to sort, but usually what we want is to sort out-of-order arrays.
This requires the use of an idea called Divide and Conquer;
What’s going on;
Just divide the target array into two halves to perform the above sorting function.
When we found that the two small arrays after splitting did not meet the conditions of my sorting function!
Hey, then I will divide the small array into two halves again, into small arrays, and then merge and sort;
ah? If you are still not satisfied, then give me more points! Give me points! !
Finally, it is divided into a pile of arrays with only one element left. It must meet the ordering conditions, right?
At this time, we merge these small arrays (numbers). Based on our hard work above, we found that the merge must be in order until there is only one merged, then it is completed!
Then here is the code idea:
The specific segmentation process is as follows:
- First, determine whether left is less than right. If this condition is not met, it means that the current subsequence has only one element or is empty. There is no need to perform splitting and merging operations and return directly.
- Calculate the middle position mid=(left + right)/2.
- By calling the mergesort function recursively, the left half of the subsequence is continued to be split and sorted (from left to mid).
- By calling the mergesort function recursively, the subsequences in the right half are continued to be split and sorted (from mid + 1 to right).
- Call the merge function to merge the left half and right half of the subsequences.
In the mergesort function, by continuously splitting the subsequences into two and performing merge operations, the entire sequence is finally sorted.
The following is the code:
void mergesort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
3. Code implementation
With the above two operations, the merge sort has been completed.
We only need to reference the mergesort function once to complete the divide and conquer directions through the function itself.
The following is the complete code of the sorting function
void merge(int arr[], int left, int mid, int right) {
int temp[100];
int i = left, j = mid + 1;
int k = left;
while (i <= mid & amp; & amp; j <= right) {
if (arr[i] < arr[j]) {
temp[k + + ] = arr[i + + ];
}
else {
temp[k + + ] = arr[j + + ];
}
}
while (i <= mid)
temp[k + + ] = arr[i + + ];
while (j <= right)
temp[k + + ] = arr[j + + ];
k = left;
while (k <= right) {
arr[k] = temp[k];
k++;
}
}
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
Three major characteristics of merge sort:
During the “passing” process, the array is divided into two equal parts, and then the sub-array is divided into two parts;
In the process of “returning”, the two ordered sub-arrays are merged into one ordered sub-array;
recursion:
The end of recursion returns the solution that is always the smallest subproblem
Recursive calls are ordinary function calls, there is no essential difference (each call has its own independent stack space)
When using recursive thinking to solve problems, you must always remind yourself what the original problem is, then what the sub-problems are!