Shell sort

Definition

Shell sort is an in-place, comparison-based sorting algorithm that sorts elements by repeatedly performing insertion sort on elements separated by a decreasing gap sequence until the gap becomes 1, at which point the array is completely sorted.

In simple terms, Shell sort is a generalized version of insertion sort that first sorts elements far apart and then gradually brings them closer together. The “gap” controls how far apart the compared elements are. A larger gap helps move elements across the array quickly, and a smaller gap fine-tunes the order near the end.

Main Content

1. Gap Sequence

The gap sequence is the most important concept in Shell sort because it determines how elements are compared and moved during each pass.
A gap is the distance between two elements being compared; for example, with a gap of 4, elements at positions 0 and 4, 1 and 5, 2 and 6, and so on are compared as part of the same sublists.

The algorithm begins with a large gap and reduces it step by step. Common gap sequences include:

n/2, n/4, n/8, ... , 1

: the simplest and most commonly taught sequence.

Hibbard sequence

: 1, 3, 7, 15, ...

Knuth sequence

: 1, 4, 13, 40, ...

Ciura sequence

: a practical sequence often used in implementations because it performs well in real cases.

A good gap sequence can greatly improve performance. A poor one may make the algorithm slower. This is one reason Shell sort is considered both simple and interesting: its efficiency depends not only on the sorting method, but also on the chosen gap pattern.

Example for an array:

[8, 5, 3, 7, 6, 2, 1, 4]

If gap = 4, then the algorithm compares:

indices 0 and 4 → 8 and 6
indices 1 and 5 → 5 and 2
indices 2 and 6 → 3 and 1
indices 3 and 7 → 7 and 4

This helps partially organize the array much faster than regular insertion sort.

2. Insertion Sort with Gaps

Shell sort uses the basic idea of insertion sort, but instead of working on adjacent elements only, it works on elements separated by a gap.
Each pass with a particular gap performs a “gapped insertion sort,” which inserts each element into the correct position among elements that are gap positions apart.

This is what makes Shell sort effective. Insertion sort is very efficient when the array is already nearly sorted, but it performs poorly when elements are far from their correct positions. Shell sort reduces that problem by moving elements long distances early in the process.

For example, suppose gap = 3 and the array is:

[12, 34, 54, 2, 3, 7]

The sublists are:

positions 0, 3 → [12, 2]
positions 1, 4 → [34, 3]
positions 2, 5 → [54, 7]

After gapped insertion sorting, the array becomes more organized. Then the gap is reduced, often to 1, and a final insertion sort finishes the job quickly because the array is already nearly sorted.

Why this helps:

Large gaps move elements toward their correct region early.
Smaller gaps refine the order.
Final pass with gap 1 is much cheaper than plain insertion sort on an unsorted array.

3. Time Complexity and Performance

Shell sort is generally faster than insertion sort for medium-sized datasets because it reduces the total amount of shifting needed.
Its exact time complexity depends heavily on the gap sequence used, which makes its analysis more complex than simpler sorting algorithms.

Common complexity observations:

Best case

: can be close to O(n log n) or even better for some sequences and nearly sorted data, but this varies.

Average case

: often around O(n^1.5) for many practical gap choices.

Worst case

: can be O(n²) for the simple gap sequence n/2, n/4, ..., 1.

Important performance notes:

Shell sort is in-place, so it uses very little extra memory.
It is not stable, meaning equal elements may change relative order.
It is usually better than simple quadratic sorts like selection sort and insertion sort for larger arrays, but slower than highly optimized O(n log n) algorithms such as merge sort or quicksort in many scenarios.

ASCII illustration of the idea:

Large gap pass -> Medium gap pass -> Small gap pass -> Final sorted array

This gradual narrowing is the key reason Shell sort works well in practice.

Working / Process

Choose an initial gap
Start with a large gap, often half the array size.
Example: for 10 elements, the initial gap may be 5.
Perform gapped insertion sort
Compare elements that are gap positions apart.
Shift larger elements to the right and insert smaller elements into their proper positions within each gap-based subarray.
Reduce the gap and repeat
Make the gap smaller and repeat the gapped insertion sort process.
Continue until the gap becomes 1, which is the final insertion sort pass that completes the sorting.

Example process for array:

[9, 8, 3, 7, 5, 6, 4, 1]

Suppose the gap sequence is 4, 2, 1.

Gap = 4

Compare and sort elements at indices (0,4), (1,5), (2,6), (3,7)
The array becomes more organized.

Gap = 2

Now sort elements at (0,2,4,6) and (1,3,5,7)
More elements move closer to their final position.

Gap = 1

Perform ordinary insertion sort on the nearly sorted array
Final arrangement becomes completely sorted

A compact visual flow:

[unsorted array] → gap = large: rough ordering → gap = smaller: finer ordering → gap = 1: final cleanup → [sorted array]

This staged process is what makes Shell sort much more efficient than directly applying insertion sort to a completely unsorted list.

Advantages / Applications

Shell sort is simple to understand and implement, especially when compared with more advanced sorting algorithms.
It is more efficient than basic quadratic sorting algorithms like insertion sort and selection sort on medium-sized or partially sorted datasets.
It sorts in place, requiring only a small amount of extra memory, which makes it useful in memory-constrained environments.

Other important uses include:

Sorting datasets where simplicity matters more than optimal theoretical performance
Educational demonstrations of gap-based algorithm design
Small to medium arrays where the overhead of advanced algorithms may not be necessary
Partially sorted data, where Shell sort can perform quite well in practice

Despite its usefulness, Shell sort is not usually preferred for very large datasets where faster and more predictable algorithms are available. Still, it remains an important algorithm in computer science because it bridges the gap between simple sorting methods and more advanced techniques.

Summary

Shell sort is a gap-based improvement over insertion sort.
It becomes faster by first sorting elements far apart and then reducing the gap.
It is in-place, easy to implement, and useful for medium-sized or partially sorted data.
Important terms to remember: gap sequence, gapped insertion sort, in-place sorting, comparison-based sorting, stability