Shell Sort
Insertion sort on items a gap apart, with the gap shrinking to 1. Far-away items move in big jumps, so the final insertion sort has little work left.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Insertion sort is slow when a small item sits far to the right: it creeps left one step at a time. Shell sort fixes this by letting items jump.
Picture lining up a class by height. First, compare students 4 places apart and swap if needed. Then 2 apart. Finally, neighbours. After the big jumps, everyone is nearly in place, and the last neighbour pass (plain insertion sort) has almost nothing to do.
The algorithm
for gap = n/2, n/4, ..., 1:
insertion sort, but compare a[j] with a[j - gap]With gap = 4, the array is really four separate small lists (indices 0, 4 · 1, 5 · 2, 6 · 3, 7), and each one is insertion-sorted.
Why it works
Insertion sort is O(n) on nearly sorted data. The large gaps make the data nearly sorted cheaply, so the final gap-1 pass is fast.
Shell sort is not stable: a jump can carry an item past an equal one.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Watch the gap go 4 → 2 → 1. By the last pass, almost nothing moves.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
void shellSort(int a[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) { // insertion sort on items gap apart
int temp = a[i];
int j = i;
while (j >= gap && a[j - gap] > temp) {
a[j] = a[j - gap];
j -= gap;
}
a[j] = temp;
}
cout << "after gap " << gap << ": ";
for (int k = 0; k < n; k++) cout << a[k] << " ";
cout << "\n";
}
}
int main() {
int a[] = {35, 33, 42, 10, 14, 19, 27, 44};
int n = sizeof(a) / sizeof(a[0]);
shellSort(a, n);
}after gap 4: 14 19 27 10 35 33 42 44 after gap 2: 14 10 27 19 35 33 42 44 after gap 1: 10 14 19 27 33 35 42 44
05Complexity
| Best case (sorted) | O(n log n) |
|---|---|
| Average case | depends on the gaps; about O(n^1.5) for n/2, n/4, … |
| Worst case (gaps n/2, n/4, …) | O(n²) |
| Extra space | O(1) |
| Stable? | No |
| In-place? | Yes |
Better gap sequences (Knuth's 1, 4, 13, 40, …) bring the worst case down to about O(n^1.5). The exam usually uses n/2, n/4, …, 1.
06Watch
Sorts 5: Shell Sort
Why this one: Short, clear explanation of why gaps help, with a hand trace.
Shell Sort: full explanation with code
Why this one: A long, slow walkthrough with code, in the style of a class lecture.
07Exam lens
Likely questions
- Trace shell sort with gaps 4, 2, 1 on
35, 33, 42, 10, 14, 19, 27, 44. - How is shell sort related to insertion sort? Why is it faster?
- Is shell sort stable? Give a reason.
Common mistakes
- Comparing neighbours (gap 1) in every pass, which is just insertion sort.
- Forgetting that the last pass must use gap = 1, or the array may not be sorted.
- Claiming it is stable. Jumps over a gap can reorder equal keys.
08Quick check
09Practice
🟢 Trace by hand
Trace shell sort (gaps 4, 2, 1) on 35, 33, 42, 10, 14, 19, 27, 44. Write the array after each gap.
Show answer
- gap 4:
14 19 27 10 35 33 42 44 - gap 2:
14 10 27 19 35 33 42 44 - gap 1:
10 14 19 27 33 35 42 44
🟡 Implement it
Change the code to use Knuth's gaps (1, 4, 13, 40, …) and count comparisons for both versions on a reversed array of 100 items.
Hint
Start with gap = 1; while (gap < n / 3) gap = 3 * gap + 1; and shrink with gap /= 3.
🔴 Solve problems
Hint
Shell sort usually passes where bubble and insertion sort time out.
Hint
Any sort works. Then try a one-pass solution with three pointers.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.