Shell Sort

Generalizes insertion sort by comparing elements far apart first, shrinking the gap each pass.

Best: O(n log n) · Avg: O(n^1.3) · Worst: O(n²) · Space: O(1)

20
90
17
93
18
69
16
57
10
36
33
61
93
52
72
Speed5
Size15
TypeScript
function shellSort(arr: number[]): number[] {
  for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < arr.length; i++) {
      let j = i;
      while (j >= gap && arr[j - gap] > arr[j]) {
        [arr[j - gap], arr[j]] = [arr[j], arr[j - gap]];
        j -= gap;
      }
    }
  }
  return arr;
}