This folder contains an implementation of Shell Sort, an efficient generalization of Insertion Sort that sorts elements far apart first and progressively reduces the gap between elements being compared. Developed by Donald Shell in 1959, it is one of the oldest non-trivial sorting algorithms that significantly outperforms basic O(n²) algorithms.
Shell Sort works by breaking the original list into smaller sublists which are then sorted using Insertion Sort. The unique aspect is that these sublists consist of elements a certain "gap" apart.
The Process:
- Start with a large gap (typically half the array length)
- Sort sublists of elements spaced by this gap using Insertion Sort
- Reduce the gap and repeat
- Continue until gap becomes 1 (standard Insertion Sort on the nearly sorted array)
The payoff is in step 4: by the time the gap reaches 1, elements are already close to their final positions, and Insertion Sort is at its fastest on nearly sorted data.
| Case | Time Complexity | Notes |
|---|---|---|
| Best Case | O(n log n) | Depends on gap sequence |
| Average Case | O(n^1.5) | Varies with gap sequence |
| Worst Case | O(n²) | With the halving sequence used here |
| Space Complexity | O(1) | In-place sorting algorithm |
On the gap sequence: this implementation uses Shell's original halving sequence (n/2, n/4, ... 1) because it is the easiest to follow. It is also the reason for the O(n²) worst case. Ciura's sequence (1, 4, 10, 23, 57, 132, 301, 701) performs markedly better in practice, and Sedgewick's reaches an O(n^4/3) worst case.
- Type: Comparison Sort
- Stability: ❌ Not stable (may change order of equal elements)
- In-place: ✅ Yes (requires only O(1) extra memory)
- Adaptive: ✅ Yes (performance depends on initial order)
- Gap Sequences: Performance heavily depends on the chosen gap sequence
shell_sort.py— implementation with commentaryshell_sort.html— interactive animation showing the gap shrinking on each round, open it in any browser