Introduction to Algorithms by CLRS version of Merge Sort
I like this version of more than the regular merge sort version because we can see much more clarity
in terms of recursion. Initially, the letters p, q, r
might looks strange but they just denote p
as the 0th index, q as a mid-point index, r as the last index
Main function's pseudocode
- For an input array A[p…r]
- Find the floor mid-point q as (p+q)/2
- mergesort(A, p, q)
- mergesort(A, q+1, r)
- merge(A, p, q, r)
Merge function's pseudocode
In the below pseudocode, setting the B and C as infinity helps us avoid running through the last remaining array for which we have to write 2 loops in the regular merge sort version. Inserting a “Sentinel” value, in this case a value that will be larger than any real value in the array, at the end of the array will make the check against it always fail. Also, sentinel value can be thought of as a value that terminates the loop.
- create B and C as new arrays
- set i and j as 0
- copy A[p..q] to B and A[q+1..r] to C
- set B’s and C’s last item as Infinity
- for k = p to r:
- if B[i] is less than C[j]
- set A[k] as B[i] and increment i
- else if B[i] is more than C[j]
- set A[k] to C[j] and increment j
- if B[i] is less than C[j]
Final Code
var input = [1, 5, 5, 2, 9, 4, 8, 7, 4, 5, 1, 0, 8, 2, 1, -1, -3]
function mergeSort(A, p, r) {
if (p >= r) return
var q = Math.floor((p + r) / 2)
mergeSort(A, p, q)
mergeSort(A, q + 1, r)
merge(A, p, q, r)
}
function merge(A, p, q, r) {
var B = [],
C = []
var i = 0,
j = 0
for (var m = p; m <= q; m++) {
B.push(A[m])
}
for (var m = q + 1; m <= r; m++) {
C.push(A[m])
}
B.push(Infinity)
C.push(Infinity)
for (var k = p; k <= r; k++) {
if (B[i] <= C[j]) {
A[k] = B[i]
i++
} else if (B[i] > C[j]) {
A[k] = C[j]
j++
}
}
}
mergeSort(input, 0, input.length - 1)
console.log(input)