# 8.1 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.

Chapter: Advanced Sorting & Searching · ~35 min · medium
URL: https://dsa.fetehadin.com/learn/shell-sort

## Mental 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

```text
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.

## C++ code: shell-sort.cpp

```cpp
#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);
}
```

Expected output:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| 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²) |

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.

## Videos

- [Sorts 5: Shell Sort](https://youtu.be/ddeLSDsYVp8) (Rob Edwards): Short, clear explanation of why gaps help, with a hand trace.
- [Shell Sort: full explanation with code](https://youtu.be/9crZRd8GPWM) (Jenny's Lectures CS IT): A long, slow walkthrough with code, in the style of a class lecture.

## Exam 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.

## Quick check

1. With n = 8 and gaps n/2, n/4, …, which gaps are used?
   A. 8, 4, 2, 1
   B. 4, 2, 1
   C. 3, 2, 1
   D. 7, 3, 1
   Answer: B. 8/2 = 4, then 2, then 1.

2. The final pass of shell sort is…
   A. a selection sort
   B. a plain insertion sort (gap 1)
   C. a merge
   D. skipped if sorted
   Answer: B. Gap 1 is ordinary insertion sort, but on an almost-sorted array, so it is fast.

3. Is shell sort stable?
   A. Yes
   B. No
   Answer: B. Equal items in different gap groups can swap order.

## Practice

**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.

Solution:

- 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`.

**Problems:**

- [Sort an Array](https://leetcode.com/problems/sort-an-array/) (medium). Hint: Shell sort usually passes where bubble and insertion sort time out.
- [Sort Colors](https://leetcode.com/problems/sort-colors/) (medium). Hint: Any sort works. Then try a one-pass solution with three pointers.

## Mastery checklist

- [ ] I can explain shell sort as gapped insertion sort.
- [ ] I can trace the gap passes by hand.
- [ ] I know it is in-place and not stable.