Time Complexity
Best: O(n log n)
Avg: O(n^(3/2))
Worst: O(n²)
Shell Sort is a generalization of Insertion Sort that allows the exchange of items that are far apart. It uses a decreasing gap sequence to progressively sort the array.
How it works:
1. Start with a large gap (typically n/2)
2. Perform a gapped insertion sort for the current gap
3. Reduce the gap (typically by half)
4. Repeat until gap is 1 (final pass is a standard insertion sort)
Time Complexity:
Best: O(n log n)
Average: O(n^(3/2)) — depends on gap sequence
Worst: O(n²) — with n/2 gap sequence
Space Complexity: O(1) — in-place
Properties:
- Not stable
- In-place
- Adaptive
Shell Sort is faster than Insertion Sort for larger arrays because it moves elements closer to their final position earlier. Performance depends heavily on the gap sequence chosen.
Related algorithms
Frequently asked questions
- What is Shell Sort?
- Shell Sort is a generalization of Insertion Sort that allows the exchange of items that are far apart. It uses a decreasing gap sequence to progressively sort the array.
- What is the complexity of Shell Sort?
- Time (average): O(n^(3/2)) — depends on gap sequence · Space: O(1)
- Who is this Shell Sort visualizer for?
- The Shell Sort visualization targets intermediate-level learners in the Sorting category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to Shell Sort?
- In the same category (Sorting) you can explore: Bubble Sort, Selection Sort, Insertion Sort. Each has an interactive visualization.