Merge Sort

1
// Merge sort (in-place interface, uses extra array internally)
2
function mergeSort(arr) {
3
  if (arr.length <= 1) return arr
4
  const mid = Math.floor(arr.length / 2)
5
  const left = mergeSort(arr.slice(0, mid))
6
  const right = mergeSort(arr.slice(mid))
7
  return merge(left, right)
8
}
9

10
function merge(a, b) {
11
  const res = []
12
  let i = 0,
13
    j = 0
14
  while (i < a.length && j < b.length) {
15
    res.push(a[i] < b[j] ? a[i++] : b[j++])
16
  }
17
  return res.concat(a.slice(i)).concat(b.slice(j))
18
}
19

20
// Usage:
21
// mergeSort([5,2,4,1,3]) -> [1,2,3,4,5]