preface

Merge sort has always been less concerned than quick sorting, after all, the space complexity is there, only in the worst case is worse than quick sorting, but others can optimize this, the probability of this worst case is very low.

Github has a look at the top JS algorithm repository, their merge sort is basically the use of the third cycle version. Of course, there are three loops, but there are actually only two loops per merge, but the code does write three loops. Some people use the concat function to implement the latter two loops, but regardless of whether the underlying principle of concat is a loop or not, other languages don’t necessarily have concat either. The algorithm, or C language thinking to write.

Of course, some students said that the number of cycles does not matter, whether it is three or one, the time complexity is exactly the same. Yes, although it looks like there are two fewer cycles, the two reduced cycles are neither nested nor repeated, but only combined with different sections of the sub-module cycles, so there is no difference in complexity.

So what’s the point? Heh heh, the triple loop code is too long, looking at the dregs, simplify a bit better.

Train of thought

Read some articles, write quite complex, pseudo code or code fragments, did not see JS version drop. The recursive part is exactly the same, but the merge() function needs to be modified a little bit

let result = [], l = 0, r = 0, i = 0
while (l < leftArr.length && r < rightArr.length) {
  result[i++] = leftArr[l] > rightArr[r] ? rightArr[r++] : leftArr[l++]
}
while (l < leftArr.length) {
  result[i++] = leftArr[l++]
}
while (r < rightArr.length) {
  result[i++] = rightArr[r++]
}
Copy the code

The original merge () function, is to put the two traverse subarray, compare the they same subscript elements, put smaller elements in new out new array, the chosen subarray A, subscript + 1 walked behind, have not been selected subarray B, subscript, and subarray behind A continue to compare elements.

One of the two subarrays must be completed first, not at the same time, so we can’t discard the subarray that is not completed. So the following two loops means to judge which one of you has not completed the cycle, the elements that have not been recycled to get on the bus!

The new array gets all the elements of the two subarrays, and becomes a larger subarray, participating in the next round of recursion

Sentinel version of the core code:

let len = leftArr.length + rightArr.length
leftArr.push(Number.MAX_VALUE)
rightArr.push(Number.MAX_VALUE)
let i = 0, l = 0, r = 0, result = []
while (i < len) {
  result[i++] = rightArr[r] > leftArr[l] ? leftArr[l++] : rightArr[r++]
}
Copy the code

If you’re using Java, you can use integer.max_value or something like that. What’s the use of that?

The first loop condition of the original is to limit the subscripts of the two subarrays to their length. The purpose of the loop is to prevent the JS array from crossing the bounds. Of course, the JS array does not give an error, but will get an unexpected undefined.

The subarray index increases by +1 only when it is selected into the result array, and the sentinel is never selected, so the subarray index must be fixed to the last digit and not out of bounds.

Now that you’re guaranteed not to cross bounds, you can safely increase the length of the loop from a single subarray to the sum of two subarrays, all at once.

JS complete source code