Merge sort implementation

Merge sort is useful and one of the easier divide-and-conquer algorithms to understand. It's easier to conceptualize than some of the other ones. A key to merge sort is that it is recursive. If you're struggling to grasp recursion, this is going to be doubly hard to understand this algorithm.

const mergeSort = nums => {
  // base case
  if (nums.length < 2) {
    return nums
  }

  const length = nums.length
  const middle = Math.floor(length / 2)
  const left = nums.slice(0, middle)
  const right = nums.slice(middle)

  return merge(mergeSort(left), mergeSort(right))
}

const merge = (left, right) => {
  const results = []
  
  while(left.length && right.length) {
    if (left[0] <= right[0]) {
      results.push(left.shift())
    }
    else {
      results.push(right.shift())
    }
  }

  // Assumption: whatever is left must be larger than what's in results array
  while(left.length) {
    results.push(left.shift())
  }
  while(right.length) {
    results.push(right.shift())
  }

  return results
}