CLRS Merge Sort in JavaScript

Regular Merge Sort and CLRS Merge Sort are essentially the same algorithm, but CLRS Merge Sort is a more specific implementation that follows the algorithm as described in the textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.

Meher Howji avatar image
··· Likes

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)