The word merge sort has nothing to do with recursion, merge is to merge two ordered arrays into a larger ordered array, but the whole sorting algorithm could be recursion related. Because merge sort can be solved recursively or iteratively.
Recursive is top-down merge sort, iterative is bottom-up merge sort. Although the two merge sorts are implemented differently, they both invoke the core method: the merge operation.
Merge operation merge
We can declare a method merge(array object, low, mid, high), assuming array[low>>>mid] and array[mid+1>>> High] are both ordered, Create an empty aux array of the same length as array before merge, and then copy the unordered sequence [low>>> High] from the original array into aux after merge. Set two cursors I and j to the starting position of AUX [low>>>mid] and AUX [mid+1>>>high].
The auxiliary array AUX does two things: compares the size of elements based on cursors I and j; And get the ordered elements in AUX one by one into the corresponding positions of the original array array.
If one of the aux sequences aux [low>>>mid] and AUX [mid+1>>>high] is already in array, the remaining sequence is placed at the end of array.
animation
Algorithm animation video address
Code
According to the criteria in the merge method code, there are four judgment cases:
1. If the left half is exhausted, take the element on the right;
2. If the right half is exhausted, take the left element.
3. If the current element on the right is less than the current element on the left, take the current element on the right;
4. If the current element on the right is greater than or equal to the current element on the left, take the current element on the left.
Top-down merge sort (recursion)
Based on a recursion that terminates if the subsequence is of length 1. The condition of recursive termination can be changed. If you use recursion to merge sort algorithm, you may encounter a large amount of data and use recursion too frequently, resulting in too much performance consumption.
So the recursive termination condition can be changed to a subsequence of length N (just enough), and then the subsequence can be interpolated or sorted more appropriately.
The idea of recursive merge sort algorithm can be divided into three processes:
Mid = low + (high-low) / 2; mid = low + (high-low) / 2;
Array [mid+1>>>high];
Merge: After the termination condition is reached, the merge operation can be carried out to merge two sorted subsequences into a new ordered sequence.
animation
Algorithm animation video address
Code
Result
Initial state [13, 9, 15, 11, 3, 7, 17, 5, 1] merge [9, 13, 15, 11, 3, 7, 17, 5, 1] merge [9, 13, 15, 3, 11, 7, 17, 5, 1] 13, 15, 7, 17, 5, 1] merge [3, 9, 11, 13, 15, 7, 17, 1, 5] merge [3, 9, 11, 13, 15, 15, 7, 17, 1, 5] merge [1, 3, 5, 7, 9, 9, 11, 13, 15, [1, 3, 5, 7, 9, 11, 13, 15, 17]
Optimization: Use inserts for small subarrays
If the amount of data is too large, you can change the recursive termination condition to deal with small-scale problems, which can improve the performance of most recursive algorithms
Code
Optimization: Merge before testing whether the array is already in order
Once the recursive termination condition is reached, there is one less judgment condition before merging. If array[mid] is less than or equal to array[mid+1], array[low>>> High] is ordered. This change does not affect recursive calls.
Code
Bottom-up merge sort (iterative method)
Bottom-up merge sort is based on loops, unlike recursion, which splits a big problem into solvable smaller problems and uses the answers to all the smaller problems to solve the big problem. Looping algorithms start from scratch, starting with small problems that can be solved and working their way up to big ones.
Iteration-based merge sort can be divided into two processes:
Merge: start from subsequence length 1 (length), merge in pairs, get 2 * length ordered sequence;
Loop: the subsequence length is changed to 2 * length and then merges in pairs, terminating until the original array has been merged.
animation
Algorithm animation video address
Code
Result
Initial state [13, 9, 15, 11, 3, 7, 17, 5, 1] merge [9, 13, 11, 11, 3, 7, 17, 5, 1] merge [9, 13, 11, 15, 3, 7, 17, 5, 1] Merge [9, 11, 13, 15, 3, 7, 5, 17, 1] merge [9, 11, 13, 15, 3, 7, 5, 17, 1] merge [9, 11, 13, 15, 3, 5, 7, 17, 1] 1] merge [3, 5, 7, 9, 11, 13, 15, 17, 1] merge [1, 3, 5, 7, 9, 11, 13, 15, 17] [1, 3, 5, 7, 9, 11, 13, 15, 17]
Like this article friends, wechat search “algorithm clear strategy” public number, watch more wonderful algorithm animation articles