How shell sort works
- Start with an interval of half the array length.
- Take a key. While the value one interval to its left is greater, copy that value one interval to the right.
- Write the key into the gap that is left.
- Do this for every position from the interval to the end, then halve the interval. The last pass has an interval of 1, which is a plain insertion sort.
What the colours mean
For each key only its group stays bright: the positions one interval apart. Black marks where the key will go, yellow is the value compared with it, and pink is a write. While values are copied to the right the key is not in the array. The currentKey chip under the bars holds it.
Shell Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n log n) | Depends on the intervals | O(n²) | O(1) | No |
The intervals here are size / 2, size / 4 and so on down to 1, the sequence Donald Shell proposed. With it the worst case is O(n²). Other sequences do better: Knuth's 1, 4, 13, 40 has a worst case of O(n1.5).
On a sorted array every pass makes one comparison per key and moves nothing, and there are about log n passes. Set the size to 30 and the order to Reversed, then run the same array through insertion sort and compare the write counters.
The C# code
The listing beside the bars is the ShellSort() method from Shell Sort in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is shell sort stable?
No. Values in different groups jump over each other, so two equal values can end up in the opposite order.
Why does shell sort end with an interval of 1?
A pass with an interval of 1 is a full insertion sort, which always leaves the array sorted. The earlier passes move values close to their final places first, so the last pass has little left to move.
How is shell sort different from insertion sort?
Insertion sort moves a value one position per step. Shell sort first moves values in long jumps between positions an interval apart, then shortens the interval until it is 1.