Shell Sort

Idea

Shell Sort (gap-based insertion) improves insertion sort: group elements by a gap, sort each group by insertion, shrink the gap, and finish with a final insertion sort when gap = 1.

Algorithm

1. Choose initial gap $gap$ and group the array.
2. Insertion sort within each group.
3. Shrink $gap$ and repeat grouping + sorting.
4. When $gap=1$, do a final insertion sort.

Pseudo-code:

for gap = n/2; gap >= 1; gap = gap/2:
    for i = gap to n-1:
        key = A[i]
        j = i - gap
        while j >= 0 and A[j] > key:
            A[j+gap] = A[j]
            j = j - gap
        A[j+gap] = key

Code Implementation

void ShellSort(int A[], int n) {
    // increment sequence: n/2, n/4, ..., 1 (better sequences such as Hibbard's can be used)
    for (int gap = n / 2; gap >= 1; gap /= 2) {
        // insertion sort within each group
        for (int i = gap; i < n; i++) {
            int key = A[i];
            int j = i - gap;
            while (j >= 0 && A[j] > key) {
                A[j + gap] = A[j];  // shift the element in the group by gap positions
                j -= gap;
            }
            A[j + gap] = key;
        }
    }
}

Choosing the Increment Sequence

• A common sequence: $n/2, n/4, \ldots, 1$ (simple, but $O(n^2)$ in the worst case)
• Hibbard’s sequence: $2^k-1, \ldots, 15, 7, 3, 1$, which gives $O(n^{3/2})$ in the worst case
• Sedgewick’s sequence: $1, 5, 19, 41, 109, \ldots$, which performs even better

The choice of the increment sequence directly affects the efficiency of Shell sort, and it is a subject of research.

Complexity

• Best: $O(n\log n)$
• Worst: $O(n^2)$ (depends on gap sequence)
• Space: $O(1)$
• Stability: unstable

Exercises

Exercise 1

Summarize the idea of Shell sort and how it differs from straight insertion sort.

Exercise 2

What are Shell sort’s time and space complexities?