Shell Sort from Scratch (2026)
Shell Sort is an in-place comparison-based sorting algorithm that generalizes Insertion Sort by allowing the exchange of items far apart. It starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. This pre-sorting makes the final Insertion Sort pass very efficient.
The algorithm was invented by Donald Shell in 1959. Its worst-case time complexity depends on the gap sequence used, with the original being O(n²). With optimized gap sequences like Hibbard's (2^k − 1), it can achieve O(n^(3/2)) or better. Shell Sort is in-place and does not require extra memory.
Gap Sequences
The gap sequence determines how quickly the algorithm reduces the interval between compared elements. Shell's original sequence halves the gap each iteration. Better sequences like Hibbard (2^k − 1), Sedgewick, or Pratt provide improved asymptotic performance.
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i], j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
}Analysis and Properties
Shell Sort is adaptive — it performs well on partially sorted arrays. It is not stable because elements may move across large gaps. Despite the nested loops, the total number of comparisons is sub-quadratic for good gap sequences. It is one of the fastest in-place algorithms for medium-sized arrays.
# Python: Shell Sort with Hibbard's gaps
def shell_sort(arr):
n, k = len(arr), 1
while (1 << k) - 1 < n:
k += 1
for g in range(k - 1, 0, -1):
gap = (1 << g) - 1
for i in range(gap, n):
temp, j = arr[i], i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = tempFrequently Asked Questions
Why use Shell Sort over Insertion Sort?
Shell Sort significantly reduces the number of element movements by first sorting distant pairs, making it much faster than Insertion Sort for medium to large arrays while remaining in-place.
What is the best gap sequence?
The Sedgewick sequence (4^k + 3×2^(k−1) + 1) is empirically among the best, achieving O(n^(4/3)) average complexity. Pratt's sequence (powers of 2 and 3) achieves O(n log² n).
Originally published on Ayodhyyya. Last updated June 1, 2026.