CLRS Merge Sort in JavaScript

CLRS merge sort is very similar to regular merge sort but uses lot less loops and applies the concept of sentinel value.

Meher Howji avatar image
··- views
A random image as the post cover
Photo by Jeremy Bezanger on Unsplash

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

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)