Tim Sort

1const RUN = 4;
2 
3function timSort(arr) {
4  const n = arr.length;
5 
6  // Sort individual runs using insertion sort
7  for (let i = 0; i < n; i += RUN) {
8    insertionSort(arr, i, Math.min(i + RUN - 1, n - 1));
9  }
10 
11  // Merge runs, doubling the merge size each time
12  for (let size = RUN; size < n; size *= 2) {
13    for (let left = 0; left < n; left += 2 * size) {
14      const mid = Math.min(left + size - 1, n - 1);
15      const right = Math.min(left + 2 * size - 1, n - 1);
16      if (mid < right) {
17        merge(arr, left, mid, right);
18      }
19    }
20  }
21 
22  return arr;
23}
24 
25function insertionSort(arr, left, right) {
26  for (let i = left + 1; i <= right; i++) {
27    const key = arr[i];
28    let j = i - 1;
29    while (j >= left && arr[j] > key) {
30      arr[j + 1] = arr[j];
31      j--;
32    }
33    arr[j + 1] = key;
34  }
35}
36 
37function merge(arr, left, mid, right) {
38  const leftArr = arr.slice(left, mid + 1);
39  const rightArr = arr.slice(mid + 1, right + 1);
40  let i = 0, j = 0, k = left;
41 
42  while (i < leftArr.length && j < rightArr.length) {
43    if (leftArr[i] <= rightArr[j]) {
44      arr[k++] = leftArr[i++];
45    } else {
46      arr[k++] = rightArr[j++];
47    }
48  }
49  while (i < leftArr.length) arr[k++] = leftArr[i++];
50  while (j < rightArr.length) arr[k++] = rightArr[j++];
51}