merge.js

function merge(left, right) {

  // REMEMBER THAT BOTH LEFT AND RIGHT ARE ALREADY ORDERED
  
  let merged = [] // result array to return
  
  let i = 0
  let j = 0
  
  while ( i < left.length && j < right.length ) {
  
    // choose the smallest from the two
    if ( left[i] <= right[j] ) {
      merged.push( left[i] )
      i++
    } else {
      merged.push( right[j] )
      j++
    }
  }

  // push all the left-over
  while( left[i] ) {
      merged.push( left[i] )
      i++
  }
  while( right[j] ) {
      merged.push( right[j] )
      j++
  }
  
  return merged
}