Explain shell sort

Shell sort (Donald Shell, 1959) is an improvement of insertion sort. Insertion sort is slow because an element moves only one position at a time. Shell sort first compares and sorts elements that are far apart, then reduces the distance (gap) step by step, and ends with a gap of 1, which is an ordinary insertion sort on an almost-sorted list.

Steps

1. Choose a gap sequence, e.g. n/2, n/4, ..., 1 (Shell's original).
2. For each gap g: treat elements g positions apart as separate sub-lists and sort each sub-list with insertion sort.
3. Reduce the gap and repeat until the gap is 1 and the list is sorted.

void shell_sort(int a[], int n) {
    int gap, i, j, t;
    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++) {
            t = a[i];
            for (j = i; j >= gap && a[j - gap] > t; j -= gap)
                a[j] = a[j - gap];          /* shift larger element */
            a[j] = t;
        }
}

Small example: 23 12 5 18, gap 2 then 1

• Gap 2: sub-lists (23, 5) and (12, 18) → 5 12 23 18.
• Gap 1: insertion sort → 5 12 18 23.

Properties

• In-place (O(1) extra space) and not stable.
• Time: worst O(n²) with Shell's gaps (better, e.g. O(n^1.5), with Knuth's gaps 1, 4, 13, 40, ...); best case near O(n log n).
• Good for medium-size lists because it is simple and fast in practice.