Shell Sort Algorithm in DSA Go

Mental Model

Shell sort improves simple sorting by comparing elements far apart first, then reducing the gap to sort closer elements, making the list more ordered step by step.

Analogy: Imagine organizing books on a shelf by first sorting every 4th book, then every 2nd book, and finally sorting all books one by one. This way, big mistakes get fixed early, making the final sorting easier.

Array: [8, 5, 3, 7, 6, 2, 4, 1]
Gap: 4
Indexes compared: 0 and 4, 1 and 5, 2 and 6, 3 and 7

Dry Run Walkthrough

Input: array: [8, 5, 3, 7, 6, 2, 4, 1]

Goal: Sort the array in ascending order using Shell sort

Step 1: Start with gap = 4, compare and sort elements 4 apart

[6, 2, 3, 1, 8, 5, 4, 7]

Why: Sorting elements far apart reduces large disorder early

Step 2: Reduce gap to 2, perform insertion sort on subarrays separated by gap 2

[3, 1, 4, 2, 6, 5, 7, 8]

Why: Closer elements are sorted to improve order further

Step 3: Reduce gap to 1, perform final insertion sort on entire array

[1, 2, 3, 4, 5, 6, 7, 8]

Why: Final pass ensures full sorted order

Result:

[1, 2, 3, 4, 5, 6, 7, 8]

Annotated Code

DSA Go

package main

import "fmt"

func shellSort(arr []int) {
	n := len(arr)
	for gap := n / 2; gap > 0; gap /= 2 {
		// Perform gapped insertion sort for this gap size
		for i := gap; i < n; i++ {
			// Save current element to insert it later
			temp := arr[i]
			j := i
			// Shift earlier gap-sorted elements up until correct location found
			for j >= gap && arr[j-gap] > temp {
				arr[j] = arr[j-gap]
				j -= gap
			}
			// Place temp at its correct position
			arr[j] = temp
		}
	}
}

func main() {
	arr := []int{8, 5, 3, 7, 6, 2, 4, 1}
	shellSort(arr)
	fmt.Println(arr)
}

for gap := n / 2; gap > 0; gap /= 2 {

reduce gap size step by step to sort elements closer and closer

for i := gap; i < n; i++ {

iterate over elements starting from current gap index

temp := arr[i]

store current element to insert it in correct position

for j >= gap && arr[j-gap] > temp {

shift elements that are greater than temp to the right

arr[j] = temp

insert temp at its correct sorted position

Output

[1 2 3 4 5 6 7 8]

Complexity Analysis

Time: O(n^(3/2)) on average because gap sequence reduces disorder efficiently but still requires multiple passes

Space: O(1) because sorting is done in place without extra arrays

vs Alternative: Faster than simple insertion sort (O(n^2)) for larger arrays because it reduces disorder early with bigger gaps

Edge Cases

empty array

function returns immediately without errors

DSA Go

for gap := n / 2; gap > 0; gap /= 2 {

array with one element

array remains unchanged as it is already sorted

DSA Go

for gap := n / 2; gap > 0; gap /= 2 {

array with all elements equal

no swaps occur, array remains the same

DSA Go

for j >= gap && arr[j-gap] > temp {

When to Use This Pattern

When you see sorting problems where simple insertion sort is too slow, and you want a faster in-place method without extra memory, reach for Shell sort because it improves insertion sort by sorting elements far apart first.

Common Mistakes

Mistake: Not reducing the gap correctly by dividing by 2 each time
Fix: Use gap /= 2 in the loop to reduce gap size stepwise

Mistake: Not shifting elements properly inside the inner loop
Fix: Shift elements greater than temp to the right before inserting temp

Summary

Shell sort sorts an array by comparing elements far apart and gradually reducing the gap to fully sort the array.

Use Shell sort when you want a faster in-place sorting than insertion sort for medium-sized arrays.

The key insight is sorting elements far apart first reduces disorder quickly, making final sorting easier.

Practice

1. What is the main idea behind the Shell Sort Algorithm?

easy

A. It uses a divide and conquer approach to split and merge arrays.

B. It sorts elements by repeatedly swapping adjacent elements only.

C. It sorts elements by comparing distant elements and gradually reducing the gap.

D. It builds a sorted array by inserting elements one by one in order.

Solution

1. Step 1: Understand Shell Sort concept

   Shell Sort improves insertion sort by comparing elements far apart, reducing the gap over iterations.

2. Step 2: Compare with other sorting methods

   Unlike bubble or insertion sort, Shell Sort starts with distant comparisons, not just adjacent swaps.

3. Final Answer:

   It sorts elements by comparing distant elements and gradually reducing the gap. -> Option C

4. Quick Check:

   Shell Sort = distant comparisons + gap reduction [OK]

Hint: Shell Sort uses gaps to compare far elements first [OK]

Common Mistakes:

• Thinking Shell Sort only swaps adjacent elements
• Confusing Shell Sort with merge or quick sort
• Assuming it inserts elements one by one without gaps

2. Which of the following is the correct way to initialize the gap variable in Shell Sort in Go?

easy

A. gap = len(arr) * 2

B. gap := len(arr) / 2

C. gap := 0

D. gap = len(arr) + 1

Solution

1. Step 1: Identify gap initialization in Shell Sort

   The gap usually starts as half the array length to compare distant elements first.

2. Step 2: Check Go syntax for variable initialization

   Using gap := len(arr) / 2 correctly declares and initializes gap in Go.

3. Final Answer:

   gap := len(arr) / 2 -> Option B

4. Quick Check:

   gap = half array length [OK]

Hint: Start gap as half array length in Go [OK]

Common Mistakes:

• Using gap larger than array length
• Initializing gap to zero which stops sorting
• Incorrect Go syntax for variable declaration

3. What will be the output of the following Go code snippet using Shell Sort on array [9, 8, 3, 7, 5]?

func shellSort(arr []int) []int {
    n := len(arr)
    for gap := n / 2; gap > 0; gap /= 2 {
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i
            for j >= gap && arr[j-gap] > temp {
                arr[j] = arr[j-gap]
                j -= gap
            }
            arr[j] = temp
        }
    }
    return arr
}

fmt.Println(shellSort([]int{9, 8, 3, 7, 5}))

medium

A. [3 5 7 8 9]

B. [9 8 7 5 3]

C. [5 3 7 8 9]

D. [3 7 5 8 9]

Solution

1. Step 1: Trace first gap iteration (gap=2)

   Compare elements 2 apart and sort: array changes from [9,8,3,7,5] to [3,8,9,7,5] then [3,5,9,7,8].

2. Step 2: Trace second gap iteration (gap=1)

   Standard insertion sort on nearly sorted array results in [3,5,7,8,9].

3. Final Answer:

   [3 5 7 8 9] -> Option A

4. Quick Check:

   Shell Sort output = sorted array [OK]

Hint: Shell Sort outputs sorted array [OK]

Common Mistakes:

• Confusing gap steps and final output
• Assuming no change after first gap
• Mixing up array indices during swaps

4. Identify the error in this Go Shell Sort code snippet:

func shellSort(arr []int) {
    n := len(arr)
    gap := n / 2
    for gap > 0 {
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i
            for j >= gap && arr[j-gap] < temp {
                arr[j] = arr[j-gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap /= 2
    }
}

medium

A. The gap should increase instead of decrease.

B. The outer loop should use for gap < n instead of gap > 0.

C. The variable temp is not initialized properly.

D. The comparison operator should be > instead of < in inner loop.

Solution

1. Step 1: Analyze inner loop comparison

   The inner loop compares arr[j-gap] and temp to decide swapping. It should move larger elements up, so condition must be arr[j-gap] > temp.

2. Step 2: Check current comparison operator

   Current code uses arr[j-gap] < temp which incorrectly moves smaller elements, breaking sort order.

3. Final Answer:

   The comparison operator should be > instead of < in inner loop. -> Option D

4. Quick Check:

   Correct comparison = > [OK]

Hint: Inner loop compares if previous element is greater [OK]

Common Mistakes:

• Using < instead of > in inner loop condition
• Increasing gap instead of decreasing
• Misplacing gap update outside loop

5. Given an array with many duplicate values, how can Shell Sort be adapted to maintain stable sorting (preserving original order of equal elements)?

hard

A. Use a stable gap sequence like Hibbard's sequence and avoid swapping equal elements.

B. Increase the gap size to skip duplicates during sorting.

C. Shell Sort cannot be made stable; use a different algorithm instead.

D. Modify the inner loop to use >= instead of > when comparing elements.

Solution

1. Step 1: Understand stability in sorting

   Stable sorting means equal elements keep their original order after sorting.

2. Step 2: Adapt Shell Sort for stability

   Using a stable gap sequence like Hibbard's and avoiding swaps when elements are equal helps maintain stability.

3. Step 3: Evaluate other options

   Using >= breaks stability, increasing gap skips elements, and claiming impossibility is incorrect.

4. Final Answer:

   Use a stable gap sequence like Hibbard's sequence and avoid swapping equal elements. -> Option A

5. Quick Check:

   Stable Shell Sort = stable gaps + no equal swaps [OK]

Hint: Use stable gap sequences and skip swapping equals [OK]

Common Mistakes:

• Using >= comparison breaking stability
• Assuming Shell Sort cannot be stable
• Increasing gap size to skip duplicates