Shell Sort Algorithm

Shell Sort is an improved version of Insertion Sort.
It works by sorting elements that are far apart and gradually reducing the gap between elements to be compared.

It starts by comparing distant elements and then reduces the gap step by step, eventually performing a final pass with a gap of 1 (which is just Insertion Sort).

How Shell Sort Works (Step-by-Step)

1. Choose a Gap

Start with a large gap (e.g., n/2, where n is array size).

2. Compare and Swap

Compare elements that are “gap” distance apart and swap them if needed.

3. Reduce the Gap

Keep reducing the gap (usually by half) and repeat the process.

4. Final Pass

When the gap is 1, perform a regular insertion sort — but the array is mostly sorted already, so it’s faster.

Example

Input: [12, 34, 54, 2, 3]
Gap Sequence: Start with gap = 2 (n/2 = 5/2 = 2)

Step 1: Gap = 2

Compare elements 2 apart:

• Compare 12 and 54
• Compare 34 and 2 → swap → [12, 2, 54, 34, 3]
• Compare 54 and 3 → swap → [12, 2, 3, 34, 54]

Step 2: Gap = 1 (Insertion Sort)

• Final sort pass → [2, 3, 12, 34, 54]

Sorted!

Shell Sort Python code:

function shellSort(arr):

    gap = len(arr) // 2

    while gap > 0:

        for i = gap to len(arr) – 1:

            temp = arr[i]

            j = i

            while j >= gap and arr[j – gap] > temp:

                arr[j] = arr[j – gap]

                j -= gap

            arr[j] = temp

        gap //= 2

Time Complexity

 Performance depends heavily on the gap sequence used (Shell, Hibbard, Knuth, etc.)

 Space Complexity

• O (1) — In-place sort (no extra space used)

 Key Points:

• Faster than Insertion Sort
• Works well for medium-sized arrays
• Not stable