Shell sort

Why this matters

Insertion sort is simple, but it is slow when a small value sits far to the right of where it belongs. Each step can only move an element one slot to the left. A value that must travel 50 slots needs 50 steps.

Shell sort fixes this by letting elements jump over long distances early on. It is named after Donald Shell, who described it in 1959. You will use it when you want a sort that needs very little extra memory, has short code, and handles medium-sized arrays well.

This lesson builds on insertion sort. The lesson on insertion sort for nearly sorted data covers why insertion sort is fast when the data is almost in order. Shell sort uses that fact in a clever way. The lesson on heap sort covers another sort with a different trade-off.

A few terms first.

• A gap is the distance between two positions in the array. Positions 2 and 7 have a gap of 5.
• A pass is one full walk over the array with one gap value.
• A move is one copy of an element from one slot into another slot. Shell sort does not swap, it shifts.
• A gap sequence is the list of gap values used in order, such as 5, 2, 1.

Insertion sort with a gap

Start with the plain insertion sort rule. Take each element and slide it left past every bigger element until it reaches its place.

Now change the distance. Instead of comparing each element with its neighbour, compare it with the element gap slots to its left. Elements at positions 0 and 5 form one group. Elements at positions 1 and 6 form another group. Each group is sorted on its own by a plain insertion sort.

The first example uses ten numbers in reverse order and a gap of 5.

#include <cstddef>
#include <iostream>
#include <vector>
 
// One gap-based insertion pass: sorts every "column" of elements that are
// `gap` apart. Returns the number of moves (copies of an element).
std::size_t gapped_insertion_pass(std::vector<int>& a, std::size_t gap) {
    std::size_t moves = 0;
    for (std::size_t i = gap; i < a.size(); ++i) {
        int current = a[i];
        std::size_t j = i;
        while (j >= gap && a[j - gap] > current) {
            a[j] = a[j - gap];
            ++moves;
            j -= gap;
        }
        a[j] = current;
    }
    return moves;
}
 
void print(const std::vector<int>& a) {
    for (int x : a) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}
 
int main() {
    std::vector<int> a{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::cout << "start:       ";
    print(a);
 
    std::size_t moves = gapped_insertion_pass(a, 5);
    std::cout << "gap 5 moves " << moves << ": ";
    print(a);
}

The loop in gapped_insertion_pass starts at index gap, not at index 1. The variable current holds the element being placed. The variable j starts at the element's position and moves left in jumps of gap. The loop stops when j drops below gap, which means there is no element gap slots to the left, or when the element to the left is not bigger than current.

Here is what the pass does on 9 8 7 6 5 4 3 2 1 0. The pairs that share a column are (9, 4), (8, 3), (7, 2), (6, 1) and (5, 0). Each pair is out of order, so each pair is swapped by shifting.

Compile and run it with g++ -std=c++20 -Wall. The output is:

start:       9 8 7 6 5 4 3 2 1 0 
gap 5 moves 5: 4 3 2 1 0 9 8 7 6 5 

The result is not sorted yet. The big values have moved right and the small values have moved left, which is what we want. The array is now easier to sort. Each value is closer to its final place.

Shrinking the gap to 1

One pass with a fixed gap does not sort the array. Shell sort runs several passes with smaller and smaller gaps. The last pass uses gap 1. A gap of 1 is plain insertion sort, so the last pass always finishes the job.

The earlier passes do most of the heavy lifting. They move values over long distances in few steps. By the time the gap is 1, most elements are near their final place, and insertion sort is fast on nearly sorted data.

The next program runs three passes with gaps 5, 2 and 1 on the same ten numbers.

#include <cstddef>
#include <iostream>
#include <vector>
 
std::size_t gapped_insertion_pass(std::vector<int>& a, std::size_t gap) {
    std::size_t moves = 0;
    for (std::size_t i = gap; i < a.size(); ++i) {
        int current = a[i];
        std::size_t j = i;
        while (j >= gap && a[j - gap] > current) {
            a[j] = a[j - gap];
            ++moves;
            j -= gap;
        }
        a[j] = current;
    }
    return moves;
}
 
void print(const std::vector<int>& a) {
    for (int x : a) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}
 
int main() {
    std::vector<int> a{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    std::cout << "start:       ";
    print(a);
 
    for (std::size_t gap = 5; gap >= 1; gap /= 2) {
        std::size_t moves = gapped_insertion_pass(a, gap);
        std::cout << "gap " << gap << " moves " << moves << ": ";
        print(a);
    }
}

The output is:

start:       9 8 7 6 5 4 3 2 1 0 
gap 5 moves 5: 4 3 2 1 0 9 8 7 6 5 
gap 2 moves 8: 0 1 2 3 4 5 6 7 8 9 
gap 1 moves 0: 0 1 2 3 4 5 6 7 8 9 

After the gap 2 pass, the array is already sorted. The gap 1 pass then finds nothing to move, so it makes 0 moves. The gap sequence here is 5, 2, 1. It was built by halving the gap: 5, then 5 / 2 = 2, then 2 / 2 = 1. Halving is one choice. Other choices are covered in the gap sequence section below.

A note on the loop. The loop condition gap >= 1 ends the loop when gap becomes 0. The loop body never runs with gap 0, so the program does not divide by zero or index with a zero gap.

A worked trace by hand

Trace one pass on a small array, with pencil and paper, before you trust the code.

Take 4 3 2 1 and a gap of 2.

• Position 2 holds 2. Compare it with position 0, which holds 4. 4 is bigger, so copy 4 into position 2. Put 2 into position 0. Now the array is 2 3 4 1. That is 1 move.
• Position 3 holds 1. Compare it with position 1, which holds 3. 3 is bigger, so copy 3 into position 3. Put 1 into position 1. Now the array is 2 1 4 3. That is 1 move.

The gap 2 pass made 2 moves and left 2 1 4 3. The gap 1 pass then runs plain insertion sort on 2 1 4 3. It moves 1 to the front, then moves 3 back past 4. That makes 2 more moves, and the array becomes 1 2 3 4.

Your hand trace should match the program's count. If it does not, check which pair you compared.

The general algorithm

With the gapped pass as a helper, the whole sort is a short loop over a list of gaps. The function below calls gapped_insertion_pass, so place it after that function in the same file.

#include <cstddef>
#include <vector>
 
// Runs one pass for each gap in the list, in the order given.
std::size_t shell_sort(std::vector<int>& a, const std::vector<std::size_t>& gaps) {
    std::size_t moves = 0;
    for (std::size_t gap : gaps) {
        moves += gapped_insertion_pass(a, gap);
    }
    return moves;
}

The rule that makes this work is simple. The gap list must end with 1. Every gap before the last can be any positive number. If the list does not end with 1, the array may stay unsorted. The mistakes section shows this.

Shell sort does not need any extra array. All the work happens inside a. That is why it is often described as an in-place sort. In-place means the sort uses only a fixed amount of extra memory, no matter how big the input is.

Gap sequence choices

The gap sequence is the main design choice in shell sort. It decides how many passes run, and how much work each pass does. Three choices are common, and each one has a different shape.

Halving: the original idea

Shell's original sequence starts near half the array length and halves each time: n / 2, n / 4, and so on down to 1. For 16 elements that gives 8, 4, 2, 1.

#include <cstddef>
#include <iostream>
#include <vector>
 
// Gap list from the original idea: n/2, n/4, ..., 1.
std::vector<std::size_t> halving_gaps(std::size_t n) {
    std::vector<std::size_t> gaps;
    for (std::size_t g = n / 2; g >= 1; g /= 2) {
        gaps.push_back(g);
    }
    return gaps;
}
 
int main() {
    std::cout << "halving gaps for 16: ";
    for (std::size_t g : halving_gaps(16)) std::cout << g << ' ';
    std::cout << '\n';
}

Output:

halving gaps for 16: 8 4 2 1 

Halving is easy to write and easy to remember. Its weakness is that the gaps are all powers of 2. When every gap except 1 is even, elements in odd positions and elements in even positions never meet until the last pass. The gap 1 pass then has to fix a lot. Shell's original sequence can take about n squared steps on some inputs, which is no better than plain insertion sort in the worst case.

Knuth's gaps: 1, 4, 13, 40

Donald Knuth described the sequence h = 3h + 1, starting from h = 1. That gives 1, 4, 13, 40, 121, and so on. Use the largest value that is at most n / 3, then count down to 1.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
 
// Knuth's gaps: 1, 4, 13, 40, ... (h = 3h + 1), up to about n / 3.
std::vector<std::size_t> knuth_gaps(std::size_t n) {
    std::vector<std::size_t> all;
    for (std::size_t h = 1; h <= n / 3; h = 3 * h + 1) {
        all.push_back(h);
    }
    std::reverse(all.begin(), all.end());
    if (all.empty()) {
        all.push_back(1);
    }
    return all;
}
 
int main() {
    std::cout << "knuth gaps for 16: ";
    for (std::size_t g : knuth_gaps(16)) std::cout << g << ' ';
    std::cout << '\n';
}

Output:

knuth gaps for 16: 4 1 

The if (all.empty()) branch covers small arrays, such as 2 elements, where n / 3 is 0 and the loop adds nothing. Without that branch, the sort would skip the gap 1 pass and leave the array unsorted.

Measuring the two sequences

The next program sorts three inputs with both sequences and counts the moves. It also checks each result against std::sort, so a wrong answer prints WRONG.

The inputs are: 16 numbers in reverse order, 16 pseudo-random numbers, and 100 pseudo-random numbers. The pseudo-random numbers come from a small formula with a fixed seed, so every run prints the same numbers.

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>
 
std::size_t gapped_insertion_pass(std::vector<int>& a, std::size_t gap) {
    std::size_t moves = 0;
    for (std::size_t i = gap; i < a.size(); ++i) {
        int current = a[i];
        std::size_t j = i;
        while (j >= gap && a[j - gap] > current) {
            a[j] = a[j - gap];
            ++moves;
            j -= gap;
        }
        a[j] = current;
    }
    return moves;
}
 
// Runs one pass for each gap in the list, in the order given.
std::size_t shell_sort(std::vector<int>& a, const std::vector<std::size_t>& gaps) {
    std::size_t moves = 0;
    for (std::size_t gap : gaps) {
        moves += gapped_insertion_pass(a, gap);
    }
    return moves;
}
 
std::vector<std::size_t> halving_gaps(std::size_t n) {
    std::vector<std::size_t> gaps;
    for (std::size_t g = n / 2; g >= 1; g /= 2) {
        gaps.push_back(g);
    }
    return gaps;
}
 
std::vector<std::size_t> knuth_gaps(std::size_t n) {
    std::vector<std::size_t> all;
    for (std::size_t h = 1; h <= n / 3; h = 3 * h + 1) {
        all.push_back(h);
    }
    std::reverse(all.begin(), all.end());
    if (all.empty()) {
        all.push_back(1);
    }
    return all;
}
 
// A simple repeatable pseudo-random generator, so every run gives the same numbers.
std::vector<int> pseudo_random(std::size_t n, std::uint32_t seed) {
    std::vector<int> v;
    std::uint32_t state = seed;
    for (std::size_t i = 0; i < n; ++i) {
        state = state * 1664525u + 1013904223u;
        v.push_back(static_cast<int>(state % 1000));
    }
    return v;
}
 
void show(const char* label, std::vector<int> data) {
    std::vector<int> expected = data;
    std::sort(expected.begin(), expected.end());
 
    std::vector<int> halving = data;
    std::size_t moves_h = shell_sort(halving, halving_gaps(data.size()));
 
    std::vector<int> knuth = data;
    std::size_t moves_k = shell_sort(knuth, knuth_gaps(data.size()));
 
    std::cout << label << "\n";
    std::cout << "  halving gaps moves: " << moves_h << (halving == expected ? " ok" : " WRONG") << "\n";
    std::cout << "  knuth gaps moves:   " << moves_k << (knuth == expected ? " ok" : " WRONG") << "\n";
}
 
int main() {
    std::vector<int> reversed;
    for (int i = 15; i >= 0; --i) {
        reversed.push_back(i);
    }
    show("reversed 16 numbers", reversed);
    show("pseudo-random 16 numbers", pseudo_random(16, 7));
    show("pseudo-random 100 numbers", pseudo_random(100, 7));
}

Output:

reversed 16 numbers
  halving gaps moves: 32 ok
  knuth gaps moves:   48 ok
pseudo-random 16 numbers
  halving gaps moves: 26 ok
  knuth gaps moves:   34 ok
pseudo-random 100 numbers
  halving gaps moves: 354 ok
  knuth gaps moves:   485 ok

On these inputs, halving made fewer moves. This does not mean halving is always better. Knuth's sequence has a better worst case in theory, and its advantage shows up on larger and harder inputs. These three runs are too small to decide the question. Also, moves are only one kind of work. Each pass also makes comparisons, and a comparison can cost time even when no move happens. The lesson on timing and counting comparisons covers that side.

The honest lesson from the table is this: the best gap sequence depends on the input size and the kind of input, and you should measure before you choose.

A bad input for halving

The worst case for halving gaps is hard to see by eye, so the next program searches for it. It tries all 40,320 orders of 8 numbers, which is every permutation of 0 through 7.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <vector>
 
std::size_t gapped_insertion_pass(std::vector<int>& a, std::size_t gap) {
    std::size_t moves = 0;
    for (std::size_t i = gap; i < a.size(); ++i) {
        int current = a[i];
        std::size_t j = i;
        while (j >= gap && a[j - gap] > current) {
            a[j] = a[j - gap];
            ++moves;
            j -= gap;
        }
        a[j] = current;
    }
    return moves;
}
 
std::size_t run(std::vector<int> a, const std::vector<std::size_t>& gaps) {
    std::size_t moves = 0;
    for (std::size_t g : gaps) moves += gapped_insertion_pass(a, g);
    return moves;
}
 
int main() {
    const std::vector<std::size_t> halving{4, 2, 1};
    const std::vector<std::size_t> one{1};
 
    std::vector<int> p(8);
    std::iota(p.begin(), p.end(), 0);
    std::size_t worst_h = 0, worst_1 = 0;
    std::vector<int> worst_input;
    do {
        std::size_t h = run(p, halving);
        if (h > worst_h) {
            worst_h = h;
            worst_input = p;
        }
        worst_1 = std::max(worst_1, run(p, one));
    } while (std::next_permutation(p.begin(), p.end()));
 
    std::cout << "n = 8, all 40320 permutations\n";
    std::cout << "worst moves with gaps 4 2 1: " << worst_h << " on input ";
    for (int x : worst_input) std::cout << x << ' ';
    std::cout << "\nworst moves with gap 1 only (plain insertion sort): " << worst_1 << "\n";
 
    std::vector<int> r(8);
    std::iota(r.begin(), r.end(), 0);
    std::reverse(r.begin(), r.end());
    std::cout << "reversed 8, gaps 4 2 1: " << run(r, halving) << " moves\n";
    std::cout << "reversed 8, gap 1 only: " << run(r, one) << " moves\n";
}

Output:

n = 8, all 40320 permutations
worst moves with gaps 4 2 1: 20 on input 7 3 5 1 6 2 4 0 
worst moves with gap 1 only (plain insertion sort): 28
reversed 8, gaps 4 2 1: 12 moves
reversed 8, gap 1 only: 28 moves

Plain insertion sort has a worst case of 28 moves for 8 numbers. Halving with gaps 4, 2, 1 has a worst case of 20 on this list, so it is better here. For larger arrays the gap is not the only factor, and the gap pattern can still produce long runs of work. Test the sequence you pick on the kinds of input you expect.

Generic version with a comparator

The sorts above only work on int. Real code sorts strings, records and custom types. The shape is the same: replace > with a comparison function that says which element should come first.

The next program is a template. It takes any type and a comparison function. The default comparison is std::less<>, which uses < on the values.

#include <algorithm>
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
 
template <typename T, typename Less = std::less<>>
void shell_sort(std::vector<T>& a, const std::vector<std::size_t>& gaps, Less less = {}) {
    for (std::size_t gap : gaps) {
        for (std::size_t i = gap; i < a.size(); ++i) {
            T current = a[i];
            std::size_t j = i;
            while (j >= gap && less(current, a[j - gap])) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = current;
        }
    }
}
 
int main() {
    std::vector<std::string> small{"oak", "elm", "to"};
    std::vector<std::string> small_shell = small;
 
    // Sort by length only. "oak" and "elm" have the same length, so they tie.
    auto by_length = [](const std::string& x, const std::string& y) {
        return x.size() < y.size();
    };
    shell_sort(small_shell, {2, 1}, by_length);
 
    std::vector<std::string> small_stable = small;
    std::stable_sort(small_stable.begin(), small_stable.end(), by_length);
 
    std::cout << "input:       ";
    for (const auto& w : small) std::cout << w << ' ';
    std::cout << "\nshell:       ";
    for (const auto& w : small_shell) std::cout << w << ' ';
    std::cout << "\nstable_sort: ";
    for (const auto& w : small_stable) std::cout << w << ' ';
    std::cout << '\n';
}

Output:

input:       oak elm to 
shell:       to elm oak 
stable_sort: to oak elm 

The less argument is a function that answers "should x come before y?". Using less(current, a[j - gap]) in place of a[j - gap] > current makes the comparison match the order you want.

The output shows a problem. "oak" and "elm" both have length 3. In the input, "oak" comes first. After shell sort, "elm" comes first. The order of tied items changed. std::stable_sort keeps "oak" before "elm".

A sort is stable when items that compare equal keep the order they had before the sort. Shell sort is not stable, because a pass with gap 2 can move an element past an equal element that sits between them. The next section shows the mistake that follows from this.

Common mistakes

Each mistake below was run with g++ 15.2.0 using -std=c++20 -Wall.

Forgetting the final gap of 1

A gap list such as 4, 2 looks reasonable, but it does not sort. The passes move elements into groups, and nothing ever compares neighbours.

#include <cstddef>
#include <iostream>
#include <vector>
 
std::size_t gapped_insertion_pass(std::vector<int>& a, std::size_t gap) {
    std::size_t moves = 0;
    for (std::size_t i = gap; i < a.size(); ++i) {
        int current = a[i];
        std::size_t j = i;
        while (j >= gap && a[j - gap] > current) {
            a[j] = a[j - gap];
            ++moves;
            j -= gap;
        }
        a[j] = current;
    }
    return moves;
}
 
int main() {
    std::vector<int> a{8, 7, 6, 5, 4, 3, 2, 1};
    for (std::size_t gap : {4, 2}) {
        gapped_insertion_pass(a, gap);
    }
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
}

Output:

2 1 4 3 6 5 8 7 

The program does not print an error. The array is simply wrong. Always end the gap list with 1, and check that the last value is 1 when you build the list.

Using a signed index with an unsigned gap

The gap has type std::size_t, which is unsigned. If the index j is an int, the comparison j >= gap mixes signed and unsigned values. The compiler warns about it.

#include <cstddef>
#include <vector>
 
void bad_pass(std::vector<int>& a, std::size_t gap) {
    for (std::size_t i = gap; i < a.size(); ++i) {
        int j = static_cast<int>(i);
        int current = a[i];
        while (j >= gap && a[j - gap] > current) {
            a[j] = a[j - gap];
            j -= gap;
        }
        a[j] = current;
    }
}
 
int main() {
    std::vector<int> v{3, 2, 1};
    bad_pass(v, 1);
    return v[0];
}

The real g++ 15.2.0 warning is:

mistake_sign.cpp: In function 'void bad_pass(std::vector<int>&, std::size_t)':
mistake_sign.cpp:8:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
    8 |         while (j >= gap && a[j - gap] > current) {
      |                ~~^~~~~~

The file name in your message is the name of your own file. The rest of the text is the same. The fix is to keep j as std::size_t, as the lesson's code does.

Removing the bounds check

The check j >= gap stops the inner loop before it reaches a position below zero. If you delete it and use .at() to access elements, the program stops with an exception. A position below zero does not look negative in an unsigned type. It wraps around to a huge number.

#include <cstddef>
#include <iostream>
#include <vector>
 
// Same pass as the lesson, but the check j >= gap is missing.
void bad_pass(std::vector<int>& a, std::size_t gap) {
    for (std::size_t i = gap; i < a.size(); ++i) {
        int current = a.at(i);
        std::size_t j = i;
        while (a.at(j - gap) > current) {
            a.at(j) = a.at(j - gap);
            j -= gap;
        }
        a.at(j) = current;
    }
}
 
int main() {
    std::vector<int> v{5, 4, 3, 2, 1};
    bad_pass(v, 2);
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

Output:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 18446744073709551614) >= this->size() (which is 5)

The number 18446744073709551614 is 2 to the power 64, minus 2. That is what j - gap becomes when j is 0 and gap is 2. Keep the j >= gap check. It is the only thing that stops the index from going below zero.

Expecting shell sort to keep ties in order

The stability example above shows that shell sort can reorder items that compare equal. If your data has ties and the order of ties matters, use std::stable_sort. Use shell sort only when you do not need that order, or when you can add a second key that breaks the tie.

Practice

Exercise 1

Run one gapped insertion pass with gap 3 on the array 5 4 3 2 1 0. Write the array after the pass and the number of moves.

Show the answer

After the pass the array is 2 1 0 5 4 3, and the pass made 3 moves. The three columns are (5, 2), (4, 1) and (3, 0). Each pair is out of order, so each pair is swapped once by shifting.

Exercise 2

Start with 4 3 2 1. Run the gap 2 pass, then the gap 1 pass. Write the array after each pass and the total number of moves.

Show the answer

After the gap 2 pass the array is 2 1 4 3, with 2 moves. After the gap 1 pass the array is 1 2 3 4, with 2 more moves. The total is 4 moves.

Exercise 3

Given the gap list 4, 2 and the input 8 7 6 5 4 3 2 1, the output in the mistakes section is 2 1 4 3 6 5 8 7. Explain in your own words why the array is not sorted, and say what single change to the gap list fixes it.

Show the answer

The passes with gaps 4 and 2 only compare elements that are 2 or 4 slots apart. The pairs in positions 0 and 1 are never compared, so the array can end with 2 before 1. Adding a final gap of 1 fixes it, because gap 1 compares neighbours. The list becomes 4, 2, 1.

Exercise 4

Write a function std::vector<std::size_t> gaps_by_three(std::size_t n) that returns the gaps n / 3, n / 9, and so on, down to 1, and never returns an empty list. Then say what the function returns for n = 2.

Show the answer

#include <cstddef>
#include <vector>
 
std::vector<std::size_t> gaps_by_three(std::size_t n) {
    std::vector<std::size_t> gaps;
    for (std::size_t g = n / 3; g >= 1; g /= 3) {
        gaps.push_back(g);
    }
    if (gaps.empty()) {
        gaps.push_back(1);
    }
    return gaps;
}

For n = 2, n / 3 is 0, so the loop adds nothing. The if branch adds 1, and the function returns {1}. The single gap 1 pass is then plain insertion sort, which sorts a 2-element array correctly.

Exercise 5

Explain why shell sort is not stable, using the three words oak, elm and to. Name the gap value that causes the problem and the pair that changes order.

Show the answer

In the first pass, with gap 2, the pair at positions 0 and 2 is oak and to. The word to is shorter, so it is moved to the front and oak moves to position 2. That places oak after elm, which was at position 1. The gap 2 pass is the step that moves oak past elm. The two words have the same length, so the order between them should have been kept, but the sort does not check for that.

Summary

• Shell sort runs insertion sort on elements that are a fixed gap apart, then runs passes with smaller gaps.
• Each pass with a large gap moves elements over long distances in few steps, so the final gap 1 pass has little work to do.
• The gap list must end with 1, or the array can stay unsorted.
• Halving gaps (n / 2, n / 4, ...) are easy to write but can be slow on some inputs. Knuth's gaps 1, 4, 13, 40 are another common choice.
• Shell sort uses no extra array and is not stable, so use std::stable_sort when the order of ties must be kept.