Shell Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Shell Sort Algorithm

Start with array

↓

Choose initial gap = n/2

↓

Perform gapped insertion sort

↓

Reduce gap: gap = gap/2

↓

Is gap > 0?

No→Sorted array

↩Back to gapped insertion sort

Shell Sort starts with a big gap and sorts elements far apart, then reduces the gap until it becomes 1, finishing with a normal insertion sort.

Execution Sample

DSA Go

arr := []int{5, 3, 8, 1, 2}
gap := len(arr)/2
for gap > 0 {
  // gapped insertion sort
  gap /= 2
}

This code sorts the array using Shell Sort by repeatedly reducing the gap and sorting elements at that gap.

Execution Table

Step	Operation	Gap	Array State	Comparison	Swap?	Description
1	Initialize gap	2	[5, 3, 8, 1, 2]	-	-	Set gap to 2 (5/2)
2	Compare arr[2] and arr[0]	2	[5, 3, 8, 1, 2]	8 vs 5	No	8 >= 5, no swap
3	Compare arr[3] and arr[1]	2	[5, 3, 8, 1, 2]	1 vs 3	Yes	1 < 3, swap
4	Array after swap	2	[5, 1, 8, 3, 2]	-	-	Array updated after swap
5	Compare arr[4] and arr[2]	2	[5, 1, 8, 3, 2]	2 vs 8	Yes	2 < 8, swap
6	Array after swap	2	[5, 1, 2, 3, 8]	-	-	Array updated after swap
7	Reduce gap	1	[5, 1, 2, 3, 8]	-	-	Gap reduced to 1
8	Compare arr[1] and arr[0]	1	[5, 1, 2, 3, 8]	1 vs 5	Yes	1 < 5, swap
9	Array after swap	1	[1, 5, 2, 3, 8]	-	-	Array updated after swap
10	Compare arr[2] and arr[1]	1	[1, 5, 2, 3, 8]	2 vs 5	Yes	2 < 5, swap
11	Array after swap	1	[1, 2, 5, 3, 8]	-	-	Array updated after swap
12	Compare arr[3] and arr[2]	1	[1, 2, 5, 3, 8]	3 vs 5	Yes	3 < 5, swap
13	Array after swap	1	[1, 2, 3, 5, 8]	-	-	Array updated after swap
14	Compare arr[4] and arr[3]	1	[1, 2, 3, 5, 8]	8 vs 5	No	8 >= 5, no swap
15	Reduce gap	0	[1, 2, 3, 5, 8]	-	-	Gap reduced to 0, sorting done

💡 Gap becomes 0, so the array is fully sorted.

Variable Tracker

Variable	Start	After Step 1	After Step 7	After Step 15
gap	undefined	2	1	0
arr	[5, 3, 8, 1, 2]	[5, 3, 8, 1, 2]	[5, 1, 2, 3, 8]	[1, 2, 3, 5, 8]

Key Moments - 3 Insights

Why do we start with a gap of n/2 instead of 1?

Starting with a larger gap allows the algorithm to move elements far apart closer to their correct position early, reducing total swaps later. See Step 1 where gap is 2, not 1.

Why do we perform insertion sort on elements separated by the gap?

Gapped insertion sort sorts elements that are 'gap' apart, partially sorting the array. This helps reduce disorder before the final pass with gap=1. See Steps 2-6 for gap=2 sorting.

Why does the gap reduce by dividing by 2 each time?

Reducing gap by half each time gradually refines the sorting from coarse to fine. This sequence is simple and effective. See Steps 7 and 15 where gap changes from 2 to 1 to 0.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after Step 6?

A [5, 1, 8, 3, 2]

B [5, 1, 2, 3, 8]

C [1, 3, 8, 5, 2]

D [5, 3, 8, 1, 2]

💡 Hint

Check the 'Array after swap' row at Step 6 in the execution table.

At which step does the gap become 1?

A Step 1

B Step 7

C Step 15

D Step 2

💡 Hint

Look for the 'Reduce gap' operation in the execution table.

If the initial gap was set to 1, what would happen?

A The array would be sorted immediately with normal insertion sort.

B The algorithm would skip sorting.

C The gap would increase automatically.

D The array would remain unsorted.

💡 Hint

Gap=1 means normal insertion sort, as shown in Steps 7-14.

Concept Snapshot

Shell Sort Algorithm:
- Start with gap = n/2
- Perform insertion sort on elements gap apart
- Reduce gap by half each iteration
- Repeat until gap = 0
- Final pass with gap=1 is normal insertion sort
- Efficient for medium-sized arrays

Full Transcript

Shell Sort sorts an array by starting with a large gap between elements and sorting those elements. The gap starts at half the array size and reduces by half each time. At each gap, a gapped insertion sort is performed, moving elements closer to their correct positions. When the gap reaches 1, a normal insertion sort finishes the sorting. This method reduces the total number of swaps compared to simple insertion sort, making it faster for medium-sized arrays.