Merge Sort

Divides array into halves, sorts each, then merges them back together.

Best: O(n log n) · Avg: O(n log n) · Worst: O(n log n) · Space: O(n)

36
20
80
88
83
57
20
73
22
40
15
17
43
48
44
Speed5
Size15
TypeScript
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(l: number[], r: number[]): number[] {
  const res: number[] = [];
  let i = 0, j = 0;
  while (i < l.length && j < r.length) {
    res.push(l[i] <= r[j] ? l[i++] : r[j++]);
  }
  return res.concat(l.slice(i), r.slice(j));
}