Shell Sort Algorithm
The shell sort algorithm speeds up insertion sort by first sorting elements that are far apart, then shrinking the gap until it is 1. Moving items long distances early leaves very little work for the final pass. Step through it below, then read how it works.
Try it: Insertion sort applied to elements that are a gap apart. The gap starts at n/2 and halves each round until it is 1, so far-apart elements move quickly. Click the Next button to perform one step at a time.
Time: about O(n log² n) to O(n²) depending on the gap sequence · Space: O(1) · Not stable
What is Shell Sort?
Shell Sort is an improved Insertion Sort. Instead of moving elements one position at a time, it first sorts elements that are far apart (a gap apart) and then reduces the gap, finishing with a normal insertion sort when the gap is 1.
Key insight: Sorting with a large gap moves out-of-place elements long distances in few steps. By the time the gap reaches 1, the list is almost sorted, which is the best case for Insertion Sort.
Shell Sort Time Complexity
| Measure | Value |
|---|---|
| Best case | O(n log n) |
| Average case | Depends on gaps (about O(n^1.3) to O(n²)) |
| Worst case | O(n²) with simple gaps |
| Space | O(1) |
| Stable | No |
For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for Shellsort.
Algorithm Steps
- Choose an initial gap, commonly n / 2.
- For each element, compare it with the element a gap behind it and insert it into its gapped sub-list.
- Halve the gap.
- Repeat until the gap is 1.
- The final gap-1 pass is an insertion sort on an almost sorted list.
Advantages and Disadvantages
Advantages
- Much faster than Insertion Sort on medium-sized lists
- In place with O(1) extra memory
- No recursion and small code
- Adaptive: faster on partially sorted data
Disadvantages
- Time complexity depends on the gap sequence and is hard to analyse
- Not stable
- Slower than O(n log n) algorithms for large inputs
Real-World Applications
- Embedded systems that need a small, non-recursive in-place sort
- Mid-sized arrays where a simple code path is preferred
- Older libraries and embedded code that need a small in-place sort
When to Use Shell Sort
Use it when you need a compact, in-place sort that beats Insertion Sort without recursion. For large data, Merge Sort, Quick Sort or Heap Sort scale better.
Shell Sort Implementation
Python
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
tmp = arr[i]
j = i
while j >= gap and arr[j - gap] > tmp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = tmp
gap //= 2
return arrJavaScript
function shellSort(arr) {
const n = arr.length;
for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < n; i++) {
const tmp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > tmp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = tmp;
}
}
return arr;
}FAQ
What is the time complexity of shell sort?
It depends on the gap sequence. With the simple n/2, n/4, … gaps used here the worst case is O(n²); better sequences such as Pratt's bring it down to O(n log² n), and practical sequences like Ciura's perform well even though their exact bound is unknown.
Is shell sort stable?
No. Elements that are a gap apart can jump over equal elements in between, so equal values may change order.
Why is shell sort faster than insertion sort?
Plain Insertion Sort moves an element one position per step. Shell sort's early large-gap passes move elements many positions at once, so by the final gap-1 pass the list is nearly sorted and insertion sort finishes quickly.
