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    
8    if (n < 2) return result;
9    
10    // Küçük diziler için insertion sort
11    if (n < 64) {
12      this.insertionSort(result, 0, n - 1);
13      return result;
14    }
15    
16    const minRun = this.getMinRunLength(n);
17    
18    // Run'ları bul ve işle
19    const runs = this.findRuns(result);
20    
21    for (const run of runs) {
22      if (run.descending) {
23        this.reverse(result, run.start, run.end);
24      }
25      
26      if (run.end - run.start + 1 < minRun) {
27        const newEnd = Math.min(run.start + minRun - 1, n - 1);
28        this.insertionSort(result, run.start, newEnd);
29        run.end = newEnd;
30      }
31    }
32    
33    // Run'ları birleştir
34    this.mergeRuns(result, runs);
35    
36    return result;
37  }
38  
39  private static getMinRunLength(n: number): number {
40    let r = 0;
41    while (n >= this.MIN_MERGE) {
42      r |= n & 1;
43      n >>= 1;
44    }
45    return n + r;
46  }
47  
48  private static insertionSort(arr: number[], left: number, right: number): void {
49    for (let i = left + 1; i <= right; i++) {
50      const key = arr[i];
51      let j = i - 1;
52      
53      while (j >= left && arr[j] > key) {
54        arr[j + 1] = arr[j];
55        j--;
56      }
57      arr[j + 1] = key;
58    }
59  }
60  
61  private static findRuns(arr: number[]): Array<{start: number, end: number, descending: boolean}> {
62    const runs = [];
63    let i = 0;
64    const n = arr.length;
65    
66    while (i < n - 1) {
67      let start = i;
68      let descending = false;
69      
70      if (arr[i] > arr[i + 1]) {
71        descending = true;
72        while (i < n - 1 && arr[i] > arr[i + 1]) {
73          i++;
74        }
75      } else {
76        while (i < n - 1 && arr[i] <= arr[i + 1]) {
77          i++;
78        }
79      }
80      
81      runs.push({ start, end: i, descending });
82      i++;
83    }
84    
85    if (i === n - 1) {
86      runs.push({ start: i, end: i, descending: false });
87    }
88    
89    return runs;
90  }
91  
92  private static reverse(arr: number[], start: number, end: number): void {
93    while (start < end) {
94      [arr[start], arr[end]] = [arr[end], arr[start]];
95      start++;
96      end--;
97    }
98  }
99  
100  private static merge(arr: number[], left: number, mid: number, right: number): void {
101    const leftArr = arr.slice(left, mid + 1);
102    const rightArr = arr.slice(mid + 1, right + 1);
103    
104    let i = 0, j = 0, k = left;
105    
106    while (i < leftArr.length && j < rightArr.length) {
107      if (leftArr[i] <= rightArr[j]) {
108        arr[k++] = leftArr[i++];
109      } else {
110        arr[k++] = rightArr[j++];
111      }
112    }
113    
114    while (i < leftArr.length) arr[k++] = leftArr[i++];
115    while (j < rightArr.length) arr[k++] = rightArr[j++];
116  }
117  
118  private static mergeRuns(arr: number[], runs: Array<{start: number, end: number}>): void {
119    let currentSize = this.MIN_MERGE;
120    const n = arr.length;
121    
122    while (currentSize < n) {
123      for (let start = 0; start < n; start += 2 * currentSize) {
124        const mid = Math.min(start + currentSize - 1, n - 1);
125        const end = Math.min(start + 2 * currentSize - 1, n - 1);
126        
127        if (mid < end) {
128          this.merge(arr, start, mid, end);
129        }
130      }
131      currentSize *= 2;
132    }
133  }
134}
135
136// Kullanım örneği
137const array = [64, 34, 25, 12, 22, 11, 90];
138console.log(TimSort.sort(array)); // [11, 12, 22, 25, 34, 64, 90]