Shell Sort generalizes Insertion Sort by allowing comparisons and swaps of elements far apart. It starts with a large gap between compared elements and reduces it progressively. By sorting widely spaced elements first, it moves elements closer to their final positions faster than Insertion Sort, achieving sub-quadratic performance.
void shellSort(vector<int>& arr) {
int n = arr.size();
for (int gap = n/2; gap > 0; gap /= 2)
for (int i = gap; i < n; i++) {
int temp = arr[i], j = i;
while (j >= gap && arr[j-gap] > temp) { arr[j] = arr[j-gap]; j -= gap; }
arr[j] = temp;
}
}Shell Sort works by sorting elements that are gap positions apart, then reducing the gap. With gap=1 it becomes plain Insertion Sort, but by then the array is nearly sorted so very few shifts are needed.
Insertion Sort is slow because it moves elements one position at a time. Shell Sort moves elements large distances in early passes, so elements are close to their final positions by the time gap=1.
The choice of gap sequence dramatically affects performance. Shells original n/2 sequence gives O(n²) worst case. Knuth (3^k-1)/2 gives O(n^1.5). Ciura's sequence gives the best practical performance.
Time complexity depends on the gap sequence and is not fully understood theoretically. Space complexity is O(1) — Shell Sort is done in-place and requires no auxiliary arrays.
Quiz coming soon for this algorithm.