Shell Sort

Shell sort is insertion sort with a head start. Plain insertion sort moves items only one step at a time, which is agony when a small value sits far from home. Shell sort fixes that by first comparing items a large gap apart — a single hop can move a stray value most of the way home — then repeating with smaller and smaller gaps until the gap is 1.

Gapped insertion sort

For a given gap g, you run an ordinary insertion sort but on elements spaced g apart instead of adjacent ones — this is gapped insertion. Large early gaps shove out-of-place values across long distances cheaply. By the time the gap shrinks to 1 (an ordinary insertion sort), the array is already nearly sorted, so that final pass barely has to move anything.

1. 1Pick a gap sequence that starts large and shrinks to 1 (e.g. n/2, n/4, …, 1).
2. 2For each gap g, run insertion sort comparing elements g apart.
3. 3Each value slides back over g-spaced larger values into its gapped slot.
4. 4Shrink the gap and repeat; the gap-1 pass finishes an almost-sorted array fast.

function shellSort(arr) {
  const n = arr.length;
  for (let gap = n >> 1; gap > 0; gap >>= 1) {  // shrinking gaps
    for (let i = gap; i < n; i++) {
      const key = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > key) {  // gapped insertion
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = key;
    }
  }
  return arr;
}