STEP-BY-STEP SHELL SORT EXAMPLE

Array: 45, 12, 78, 23, 56, 9, 67, 34, 89, 41
Size (n) = 10

We use the most common gap sequence: n/2, n/4, …, 1
(i.e., 5 → 2 → 1)

Initial Array

Index:  0   1   2   3   4   5   6   7   8   9
Value: 45  12  78  23  56   9  67  34  89  41

PASS 1 – Gap = 5 (10/2 = 5)

We compare and swap elements that are 5 positions apart.

Sub-lists formed (gap = 5):
- Group 1: indices 0, 5 → [45, 9]
- Group 2: indices 1, 6 → [12, 67]
- Group 3: indices 2, 7 → [78, 34]
- Group 4: indices 3, 8 → [23, 89]
- Group 5: indices 4, 9 → [56, 41]

Perform Insertion Sort on each group:

1. [45, 9] → 9 < 45 → swap → 9, 45
2. [12, 67] → already sorted
3. [78, 34] → 34 < 78 → swap → 34, 78
4. [23, 89] → already sorted
5. [56, 41] → 41 < 56 → swap → 41, 56

Array after Gap = 5:

9   12   34   23   41   45   67   78   89   56

PASS 2 – Gap = 2 (5/2 = 2)

Now compare elements 2 positions apart.

Sub-lists formed:
- Group 1: indices 0,2,4,6,8 → [9, 34, 41, 67, 89]
- Group 2: indices 1,3,5,7,9 → [12, 23, 45, 78, 56]

Insertion sort on each:

Group 1: 9, 34, 41, 67, 89 → already sorted
Group 2: 12, 23, 45, 78, 56
→ 56 needs to move left
→ 12, 23, 45, 56, 78

So we get:

Index:  0   1   2   3   4   5   6   7   8   9
Value:  9  12  34  23  41  45  67  56  89  78   → wait, no!

Correct step-by-step insertion in Group 2:

Original Group 2 positions:
1:12, 3:23, 5:45, 7:78, 9:56

• Take 56 (index 9), compare with 78 → 56 < 78 → shift 78 right
• Compare 56 with 45 → 56 > 45 → stop → place 56 at index 7
• Now array becomes: 9, 12, 34, 23, 41, 45, 67, 56, 89, 78

Wait — 78 was at index 7, shifted to index 9 → correct!

After full Gap = 2:

9   12   34   23   41   45   67   56   89   78

Still not fully sorted, but much better!

PASS 3 – Gap = 1 (final insertion sort)

Now normal Insertion Sort on whole array:

Start:  9   12   34   23   41   45   67   56   89   78

• 23 → move left → 9, 12, 23, 34, 41, 45, 67, 56, 89, 78
• 41 → already in place
• 45 → already in place
• 67 → already in place
• 56 → move left → 9, 12, 23, 34, 41, 45, 56, 67, 89, 78
• 89 → already in place
• 78 → move left → 9, 12, 23, 34, 41, 45, 56, 67, 78, 89

Final Sorted Array:

9   12   23   34   41   45   56   67   78   89

Summary Table (Step-by-Step)

Shell Sort reduces the number of shifts compared to pure insertion sort — that’s why it’s faster in practice!

Now you can draw this on paper or explain in viva with 100% confidence!