Overview
Shell Sort improves on insertion sort by moving values toward their final positions with large gaps before finishing with small gaps.
CoreSource checked
Shell Sort
Sorts by comparing items far apart, then gradually reducing the gap.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Intermediate
- Family
- Gap Sort
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Diminishing Increment Sort
Core Concepts
comparison rulein-place updateexisting runsgap sortordering invariantcomparison or key rulearray rearrangement
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n^1.5)
Worst
O(n^2)
Space
O(1)
When to Use
- Use Shell Sort when you need to sort values using shrinking gaps.
- Use it for small embedded sorts with inputs like array of comparable values.
- Use it when ordered output makes later searching, ranking, or presentation easier.
- Use it when the Gap Sort tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when a partial order, top-k result, or streaming approach would answer the question with less work.
- Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
- Avoid it when the required output is not sorted array.
What It Does
- Sorts values using shrinking gaps
- Moves distant out-of-order items earlier than insertion sort
Use Cases
- Small embedded sorts
- Teaching gap-based sorting
- In-place sorting with simple code
Inputs
- Array of comparable values
- Gap sequence
Outputs
- Sorted array
Pseudocode
- 1.Choose a sequence of gaps
- 2.For each gap, insertion sort values separated by that gap
- 3.Reduce the gap
- 4.Finish when the gap is one
Canonical Example
- Input
- values = [5, 1, 4, 2]
- Output
- values = [1, 2, 4, 5]
- Explanation
- Shell Sort: The algorithm reorders the values so later operations can read them in ascending order.
Implementation Notes
- Keep the input contract explicit: Array of comparable values; Gap sequence.
- Use this step as the implementation spine: Choose a sequence of gaps.
- Then preserve the next state change: For each gap, insertion sort values separated by that gap.
- Test with empty input, one item, duplicates, and already sorted values.
Common Pitfalls
- Performance depends heavily on the chosen gap sequence.
- Forgetting to define how equal values and custom comparison rules should behave.
- Returning sorted array without handling empty, invalid, or boundary inputs.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow distant values comparing across gaps that shrink over time.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 4: Choose a sequence of gaps
gapped-array-sortNotes
Shell Sort operates in O(n^1.5) time and O(1) space within the Gap Sort family. Often compared with Insertion Sort and Bucket Sort.
Sources (2)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSorting and searching reference covering Shell Sort comparison model, probe strategy, network structure, or pass schedule.
Shell High-Speed Sorting
PaperOriginal Shellsort reference for gap-based insertion passes over internal-memory lists.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageImproves onInsertion Sort
Shell sort improves insertion sort by allowing early gapped exchanges before the final insertion pass.
Related Algorithms
Tags
Comparison SortIn PlaceAdaptive Sort