Merge Sort

Thinking:

1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sublists of above half he size
3. Sort each sublist recursively by re-applying merge sort
4. Merge the two sublists back into one sorted list

// O(n*log(n))
let arr = [3, 5, 14, 28, 8, 23]

const MergeSort = (arr) => {
  if (arr.length < 2) return arr
  let mid = Math.floor(arr.length / 2)
  let left = MergeSort(arr.slice(0, mid))
  let right = MergeSort(arr.slice(mid))
  return Merge(left, right)
}

const Merge = (l, r) => {
  let result = []
  while (l.length > 0 && r.length > 0) {
    result.push(l[0] < r[0] ? l.shift() : r.shift())
  }
  return result.concat(r.length ? r : l)
}

console.log(MergeSort(arr))