🐚 Shell Sort

Eine optimierte Version von Insertion Sort, die Elemente über größere Distanzen hinweg vergleicht und die Lücke (Gap) schrittweise verkleinert.

Complexity

Zeit:O(n log² n)

Platz:O(1)

Code Snippet

for (let gap = Math.floor(n/2); gap > 0; gap = Math.floor(gap/2)) {
  for (let i = gap; i < n; i++) {
    let temp = arr[i];
    let j = i;
    while (j >= gap && arr[j - gap] > temp) {
      arr[j] = arr[j - gap];
      j -= gap;
    }
    arr[j] = temp;
  }
}

Speed