Shell Sort: Gap Sequences and Cost
Run insertion sort on elements a gap apart, shrink the gap, and finish with an ordinary pass over a nearly sorted array.
How Shell Sort Works
Shell sort is insertion sort with one change: instead of comparing neighbours, it compares elements a fixed distance apart, then repeats with a smaller distance. That single change breaks insertion sort's central weakness — a small value stranded at the far right has to shift past every element one position at a time — because a large gap moves it most of the way in a single swap.
- Pick a gap sequence a decreasing list of distances ending in 1, such as n/2, n/4, down to 1.
- Run a gapped insertion sort for the current gap, sort each interleaved subsequence of elements that distance apart.
- Shrink the gap move to the next value in the sequence and repeat over the whole array.
- Finish at gap 1 the last pass is ordinary insertion sort, but now on data that is already nearly sorted.
- Stop the array is sorted, having done far less shifting than plain insertion sort would.
- Each pass sorts several interleaved subsequences, not the whole array
- The gap must reach 1, or the array is not guaranteed sorted
- Early passes are cheap because each subsequence is short
- The final pass is fast because the data is nearly ordered by then
Why Distant Swaps Win
Insertion sort's cost is proportional to the number of inversions — pairs that are out of order relative to each other. Each adjacent swap removes exactly one inversion, so an array with O(n²) inversions costs O(n²) work no matter how the loop is written. That bound is what shell sort attacks.
A swap across a gap of g can remove up to g inversions at once, because it jumps a value past everything in between. Running the large gaps first therefore destroys most of the disorder cheaply, and each subsequent pass has less to do. By the time the gap reaches 1, the array is close enough to sorted that the final insertion pass is nearly linear.
This is why shell sort is worth knowing even though it is rarely the fastest choice: it is the clearest demonstration that the same algorithm becomes a different algorithm when the access pattern changes. Nothing about the comparison or the shift changed — only the distance.
- Insertion sort's cost is the inversion count
- An adjacent swap removes one inversion; a gapped swap removes up to g
- Large gaps first, so later passes start from a nearly ordered array
- The final gap-1 pass is what guarantees correctness
Sort with shell sort
def shell_sort(values):
gap = len(values) // 2
while gap > 0:
# A gapped insertion sort: same shifting, but g positions at a time.
for i in range(gap, len(values)):
current = values[i]
j = i
while j >= gap and values[j - gap] > current:
values[j] = values[j - gap]
j -= gap
values[j] = current
gap //= 2
return values
print(shell_sort([8, 5, 3, 9, 1, 6]))#include <iostream>
#include <vector>
using namespace std;
// Shell sort: insertion sort over elements a gap apart, shrinking to 1.
vector<int> shellSort(vector<int> values) {
int n = (int)values.size();
for (int gap = n / 2; gap > 0; gap /= 2) {
// A gapped insertion sort: same shifting, but gap positions at a time.
for (int i = gap; i < n; i++) {
int current = values[i];
int j = i;
while (j >= gap && values[j - gap] > current) {
values[j] = values[j - gap];
j -= gap;
}
values[j] = current;
}
}
return values;
}
int main() {
for (int v : shellSort({8, 5, 3, 9, 1, 6})) cout << v << " ";
cout << endl;
return 0;
}import java.util.Arrays;
public class ShellSort {
// Shell sort: insertion sort over elements a gap apart, shrinking to 1.
static int[] shellSort(int[] values) {
int n = values.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
// A gapped insertion sort: same shifting, gap positions at a time.
for (int i = gap; i < n; i++) {
int current = values[i];
int j = i;
while (j >= gap && values[j - gap] > current) {
values[j] = values[j - gap];
j -= gap;
}
values[j] = current;
}
}
return values;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(shellSort(new int[]{8, 5, 3, 9, 1, 6})));
}
}Step through it
Running on [8, 5, 3, 9, 1, 6]
The Gap Sequence Sets the Complexity
Shell sort has no single complexity, which makes it unusual and a common exam question. The bound depends entirely on the gap sequence, and finding the best one is still an open problem.
Shell's original sequence — repeatedly halving n — is O(n²) in the worst case, because halving keeps even and odd positions from interacting until the very last pass. Knuth's sequence (1, 4, 13, 40, …, generated by 3k + 1) gives O(n^1.5), and Sedgewick's gives O(n^4/3). The best known bounds are around O(n log²n), still short of the O(n log n) that merge and heap sort guarantee.
In practice shell sort occupies a narrow but real niche: it is in-place, needs no recursion and no extra memory, and its code is short. That makes it a reasonable choice for embedded systems and for sorting inside constrained environments where quicksort's stack or merge sort's buffer are unwelcome. It is also not stable — a gapped swap can jump a value over an equal one — so it cannot be used where multi-key sorting matters.
| Gap sequence | Formula | Worst case | Note |
|---|---|---|---|
| Shell (original) | n/2, n/4, ..., 1 | O(n squared) | Even and odd positions stay separate until the end |
| Knuth | 1, 4, 13, 40, ... (3k+1) | O(n^1.5) | Simple to generate, a common default |
| Sedgewick | 1, 5, 19, 41, 109, ... | O(n^4/3) | Better bound, more complex to derive |
| Ciura (empirical) | 1, 4, 10, 23, 57, 132, ... | unproven | Found by experiment, fastest in practice |
- No single complexity — it is a property of the gap sequence
- Halving is O(n squared); Knuth's 3k+1 gives O(n^1.5)
- In-place, O(1) space, no recursion — good for constrained systems
- Not stable, because a gapped swap can jump over an equal value
On Paper: Sorting [8, 5, 3, 9, 1, 6]
Sort [8, 5, 3, 9, 1, 6] with gaps 3 then 1. Six elements, so the first gap is 3.
- Input:
[8, 5, 3, 9, 1, 6] - Gaps: 3, then 1
- Each pass: insertion sort on elements that distance apart
At gap 3 there are three interleaved pairs: positions 0 and 3 hold 8 and 9 (already in order), positions 1 and 4 hold 5 and 1 (swap), positions 2 and 5 hold 3 and 6 (in order). One swap gives [8, 1, 3, 9, 5, 6]. Note that the 1 moved three places for a single swap — plain insertion sort would have needed three separate shifts.
At gap 1 the pass is ordinary insertion sort, but the array is now much closer to sorted: [8, 1, 3, 9, 5, 6] needs only a handful of shifts to reach [1, 3, 5, 6, 8, 9]. Compare that with running insertion sort on the original array, where the 1 alone would have cost four shifts.
- Gap 3 compares (0,3), (1,4) and (2,5) as three separate pairs
- Swapping 5 and 1 moves the 1 three positions at once
- Gap 1 is plain insertion sort on a nearly sorted array
- Fewer total shifts than insertion sort on the original input