Tim Sort

Splits array into small runs sorted with insertion sort, then merges runs using merge sort.

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

74
13
78
36
74
54
75
28
71
91
86
24
92
39
90
Speed5
Size15
TypeScript
function timSort(arr: number[]): number[] {
  const RUN = 8;
  for (let i = 0; i < arr.length; i += RUN)
    insertionSort(arr, i, Math.min(i + RUN, arr.length));
  for (let size = RUN; size < arr.length; size *= 2)
    for (let lo = 0; lo < arr.length; lo += 2 * size)
      merge(arr, lo, Math.min(lo + size, arr.length), Math.min(lo + 2 * size, arr.length));
  return arr;
}
function insertionSort(a: number[], lo: number, hi: number) {
  for (let i = lo + 1; i < hi; i++) {
    let j = i - 1, k = a[i];
    while (j >= lo && a[j] > k) a[j + 1] = a[j--];
    a[j + 1] = k;
  }
}
function merge(a: number[], lo: number, mid: number, hi: number) {
  const l = a.slice(lo, mid), r = a.slice(mid, hi);
  let i = 0, j = 0, k = lo;
  while (i < l.length && j < r.length) a[k++] = l[i] <= r[j] ? l[i++] : r[j++];
  while (i < l.length) a[k++] = l[i++];
  while (j < r.length) a[k++] = r[j++];
}