mergesort.js

function mergesort (arr) {
  let totalOperations = 0
  // this is just to debounce the logging
  let timeout
  function debouncedLog () {
    clearTimeout(timeout)
    timeout = setTimeout(() => console.log(`${totalOperations} operations`), 500)
  }
  function split (unsorted) {
    totalOperations++
    if (unsorted.length < 2) {
      totalOperations++
      // the array is either length 0 or 1, so it must already be sorted
      return unsorted
    }
    // find the middle index of this array
    let mid = Math.floor(unsorted.length / 2)
    totalOperations++
    // split the array in half
    let left = unsorted.slice(0, mid)
    totalOperations++
    // get the other half
    let right = unsorted.slice(mid, unsorted.length)
    totalOperations++
    return merge(split(left), split(right))
  }

  function merge (left, right) {
    totalOperations++
    // console.log(left, right)
    let sorted = []
    let il = 0
    let ir = 0
    while (il < left.length && ir < right.length) {
      totalOperations++
      if (left[il] <= right[ir]) {
        sorted.push(left[il++])
      } else {
        sorted.push(right[ir++])
      }
    }
    debouncedLog()
    totalOperations++
    return sorted.concat(left.slice(il)).concat(right.slice(ir))
  }

  // kick the whole thing off
  return split(arr)
}

module.exports = mergesort