Shell sort
Shell sort is insertion sort generalised to compare and shift values that are a fixed gap apart rather than adjacent. It starts with a large gap — half the array length, here — and after a full pass at each gap, halves the gap and repeats, finishing with a gap of one, which is ordinary insertion sort on an array that earlier passes have already roughly ordered.
When it is the right choice
Shell sort is worth reaching for when insertion sort is nearly fast enough but n is a bit too large for its O(n²) worst case, and an in-place sort with no recursion is preferred over quicksort or merge sort. It is rarely the fastest option available, but it is simple to implement, and its performance depends heavily on the choice of gap sequence — the halving sequence used here is the simplest, not the best known.
How it works
- Set the gap to half the array length.
- For each position from the gap to the last, remember its value as the one being inserted, exactly as insertion sort does, but comparing values a gap-width apart instead of adjacent ones.
- While the value one gap-width to the left is greater, shift it one gap-width to the right.
- Place the remembered value into the gap the shifting left behind.
- Once every position has been processed at this gap, halve the gap and repeat; once the gap reaches zero, the array is sorted.
Worth noticing
- At a gap of one, this is exactly insertion sort — the earlier, larger-gap passes are what make that final pass fast, by moving far-out-of-place values most of the way home early.
- Its performance depends on the gap sequence: the simple halving sequence used here has a known O(n²) worst case, while other published sequences do better, which is why "Shell sort" names a family of algorithms rather than one.
- It is not stable: a value can be shifted past an equal value that a smaller gap has not yet compared them at.
Cost
- Best
- O(n log n)
- Average
- O(n^1.3)
- Worst
- O(n²)
- Extra space
- O(1)
- Stable
- No