Annotated Merge Sort in JavaScript

mergesort.js

// Netto Farah
// Feb 11 2017

function mergeSort(array) {
  // Clone array so we don't modify the input.
  // This shouldn't be necessary in most cases
  array = array.slice(0, array.length)

  // msort is what we use to divide the problem
  function msort(array, low, high) {
    // Our base case is when low and high are the same.
    // This will happen as we start to subdivide the array, until we reach
    // a point where the array is no longer divisible
    if (low === high) {
      return
    }

    // Make sure we round the middle number
    let middle = Math.floor((low + high) / 2)

    // Start by tackling the left side of the array
    msort(array, low, middle)

    // And keep going with the right side
    msort(array, middle + 1, high)

    // Merge the sub arrays
    merge(array, low, middle, high)
  }

  // `merge` will create two buffer queues that will take all elements of the
  // left and right sides of the current sub array.
  function merge(array, low, middle, high) {
    let buffer1 = []
    let buffer2 = []

    // buffer1 takes in all items from low to middle
    for (var i = low; i <= middle; i++) {
      // push will add an element to the end of an array
      buffer1.push(array[i])
    }

    // and buffer 2 takes in all items from middle + 1 to high
    for (var j = middle + 1; j <= high; j++) {
      buffer2.push(array[j])
    }

    // k is an index variable we'll use to keep track of our progress as we
    // visit every item in the sub array we're working on
    let k = low

    // This is the meat of `merge`.
    // The idea here is to always peak the smallest of the elements in front
    // of both queues at each pass.
    //
    // We can then replace array[k] with the smallest of the two elements in
    // the front of our queues.
    //
    // We also need to make sure we stop after at least one of the queues is empty.
    while (buffer1.length && buffer2.length) {
      // Pick the smallest of the both candidates.
      // And then replace array[k] with one of them
      if (buffer1[0] < buffer2[0]) {
        // when buffer1 holds the smallest element in its front
        array[k] = buffer1.shift()
      } else {
        // when buffer2 holds the smallest element
        array[k] = buffer2.shift()
      }

      k++
    }

    // After the while loop is over we could possibly be left with k < high.
    // If that happens, it means either buffer1 or buffer2 still contains 1 element.
    //
    // It is all fine though, because we know the everything is sorted from low -> k

    // This will empty buffer1
    while (buffer1.length) {
      array[k] = buffer1.shift()
      // k keeps moving forward
      k++
    }

    // We'll empty buffer2 too
    while (buffer2.length) {
      array[k] = buffer2.shift()
      k++
    }

    // by now k == high and we've merged the two sub arrays
  }

  // This is where everything actually starts
  // We'll go from the beginning of the array all the way to the end.
  msort(array, 0, array.length - 1)

  return array
}

let testArray = [4, 1, 5, 6, 2, 5, 1, 6, 7, 8, 2, 4, 5, 0]
let sorted = mergeSort(testArray)

console.log('original', testArray, testArray.length)
console.log('sorterd ', sorted, sorted.length)