C++UCS301
Sorting AlgorithmsC++17

Shell Sort

Shell sort performs insertion sorts over decreasing gaps so distant inversions are removed before the final gap-one pass.

What to understand

  • Gap sequences
  • Gapped insertion sort
  • In-place operation
  • Complexity dependence on gaps

Remember this

  1. 1Ends with gap 1
  2. 2Usually faster than O(n²) elementary sorts
  3. 3Not stable
  4. 4Worst-case depends on the gap sequence

Detailed notes

Shell sort generalises insertion sort by first sorting elements far apart. Large gaps move badly displaced values quickly; decreasing gaps reduce remaining local disorder before the mandatory gap-one insertion pass.

Its exact complexity depends on the chosen gap sequence. The simple halving sequence is easy to teach, while sequences such as Knuth or Ciura usually perform better.

How it works

  1. 1Select a decreasing sequence ending in one.
  2. 2For each gap, run insertion sort on interleaved subsequences.
  3. 3Move values by gap positions rather than one position.
  4. 4Finish with ordinary insertion sort at gap one.

Where it is used

  • Medium-sized arrays with tight memory
  • Embedded implementations needing simple in-place code
  • Improving insertion sort without recursion

Common mistakes

  • Using a gap sequence that never reaches one
  • Quoting one universal complexity for all gaps
  • Calling the algorithm stable despite long-distance moves

Complexity analysis

OperationBestAverageWorstExtra space
Sort≈O(n^1.5)≈O(n^1.5)O(n²)O(1)

C++ implementation

C++17 reference
main.cpp

Shell sort with halving gaps

More advanced gap sequences improve performance, but the core gapped insertion idea is unchanged.

void shellSort(vector<int>& values) {
    for (int gap = values.size() / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < static_cast<int>(values.size()); ++i) {
            int current = values[i], j = i;
            while (j >= gap && values[j - gap] > current) {
                values[j] = values[j - gap];
                j -= gap;
            }
            values[j] = current;
        }
    }
}
12 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.