Tim Sort Algoritması

1class TimSort {
2  private static MIN_MERGE = 32;
3  
4  public static sort(arr: number[]): number[] {
5    const result = [...arr];
6    const n = result.length;
7    if (n < 2) return result;
8    
9    if (n < 64) {
10      this.insertionSort(result, 0, n - 1);
11      return result;
12    }
13    
14    const minRun = this.getMinRunLength(n);
15    const runs = this.findRuns(result, minRun);
16    this.mergeRuns(result, runs);
17    return result;
18  }
19  
20  private static getMinRunLength(n: number): number {
21    let r = 0;
22    while (n >= this.MIN_MERGE) {
23      r |= n & 1;
24      n >>= 1;
25    }
26    return n + r;
27  }
28  
29  private static insertionSort(arr: number[], left: number, right: number): void {
30    for (let i = left + 1; i <= right; i++) {
31      const key = arr[i];
32      let j = i - 1;
33      while (j >= left && arr[j] > key) {
34        arr[j + 1] = arr[j];
35        j--;
36      }
37      arr[j + 1] = key;
38    }
39  }
40  
41  private static findRuns(arr: number[], minRun: number): { start: number; end: number }[] {
42    const runs: { start: number; end: number }[] = [];
43    let i = 0;
44    const n = arr.length;
45    
46    while (i < n) {
47      const start = i;
48      while (i < n - 1 && arr[i] <= arr[i + 1]) i++;
49      const runLength = i - start + 1;
50      if (runLength < minRun && i < n - 1) {
51        i = Math.min(start + minRun - 1, n - 1);
52        this.insertionSort(arr, start, i);
53      }
54      runs.push({ start, end: i });
55      i++;
56    }
57    return runs;
58  }
59  
60  private static mergeRuns(arr: number[], runs: { start: number; end: number }[]): void {
61    let currentSize = this.MIN_MERGE;
62    const n = arr.length;
63    while (currentSize < n) {
64      for (let start = 0; start < n; start += 2 * currentSize) {
65        const mid = Math.min(start + currentSize - 1, n - 1);
66        const end = Math.min(start + 2 * currentSize - 1, n - 1);
67        if (mid < end) this.merge(arr, start, mid, end);
68      }
69      currentSize *= 2;
70    }
71  }
72  
73  private static merge(arr: number[], left: number, mid: number, right: number): void {
74    const leftArr = arr.slice(left, mid + 1);
75    const rightArr = arr.slice(mid + 1, right + 1);
76    let i = 0, j = 0, k = left;
77    while (i < leftArr.length && j < rightArr.length) {
78      if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
79      else arr[k++] = rightArr[j++];
80    }
81    while (i < leftArr.length) arr[k++] = leftArr[i++];
82    while (j < rightArr.length) arr[k++] = rightArr[j++];
83  }
84}