Shell Sort Algorithm in DSA Python

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 sorted step by step.

Analogy: Imagine organizing books on a shelf by first comparing books far apart, then gradually comparing books closer together until all are in order.

Array: [8, 5, 3, 7, 6, 2, 4, 1]
Initial gap: 4
Indexes compared: 0 -> 4, 1 -> 5, 2 -> 6, 3 -> 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 moves bigger elements towards the end early

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

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

Why: Sorting closer elements refines order after big jumps

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 order by comparing adjacent elements

Result:

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

Annotated Code

DSA Python

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]  # shift element right
                j -= gap  # move j backward by gap
            arr[j] = temp  # insert temp at correct position
        gap //= 2  # reduce gap

# Driver code
array = [8, 5, 3, 7, 6, 2, 4, 1]
shell_sort(array)
print(array)

gap = n // 2

initialize gap to half the array length to start with far apart comparisons

while gap > 0:

repeat sorting passes while gap is positive

for i in range(gap, n):

iterate over elements starting from gap to end for insertion sort

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

shift elements that are greater than temp to the right by gap

arr[j] = temp

insert temp at its correct position in the subarray

gap //= 2

reduce gap to refine sorting with closer elements

Output

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

Complexity Analysis

Time: O(n^(3/2)) average and worst case because gap sequence reduces comparisons gradually

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

vs Alternative: Faster than simple insertion sort (O(n^2)) on large arrays because it moves elements farther apart early

Edge Cases

empty array

function returns immediately with no changes

DSA Python

while gap > 0:

array with one element

array remains unchanged as it is already sorted

DSA Python

while gap > 0:

array with all elements equal

no swaps occur, array remains the same

DSA Python

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

When to Use This Pattern

When you see sorting problems where simple insertion sort is too slow, try Shell sort because it speeds up sorting by comparing elements far apart first.

Common Mistakes

Mistake: Not reducing the gap correctly, causing infinite loops or incorrect sorting
Fix: Ensure gap is reduced by integer division gap //= 2 each iteration

Mistake: Incorrectly shifting elements inside the inner while loop, overwriting values prematurely
Fix: Use a temporary variable to hold the current element and shift others before inserting it

Summary

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

Use Shell sort when you want a faster alternative to insertion sort for medium-sized arrays.

The key insight is that sorting distant elements first reduces disorder quickly, making final passes faster.

Practice

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

easy

A. It uses a pivot element to partition the list into smaller parts.

B. It sorts elements by repeatedly swapping adjacent elements until sorted.

C. It divides the list into two halves and sorts each half separately.

D. It sorts elements by comparing and swapping distant elements first, then reducing the gap.

Solution

1. Step 1: Understand Shell Sort's approach

   Shell Sort starts by sorting pairs of elements far apart from each other, then progressively reduces the gap between elements to be compared.

2. Step 2: Compare with other sorting methods

   Unlike bubble sort (adjacent swaps) or quicksort (pivot partition), Shell Sort uses a gap sequence to improve efficiency.

3. Final Answer:

   It sorts elements by comparing and swapping distant elements first, then reducing the gap. -> Option D

4. Quick Check:

   Shell Sort = Distant element comparisons first [OK]

Hint: Remember: Shell Sort reduces gap size step-by-step [OK]

Common Mistakes:

• Confusing Shell Sort with bubble sort
• Thinking it always compares adjacent elements first
• Mixing it up with quicksort's pivot method

2. Which of the following is the correct way to start the gap sequence in Shell Sort for a list of length n?

easy

A. gap = n

B. gap = 1

C. gap = n // 2

D. gap = n * 2

Solution

1. Step 1: Identify the initial gap value

   Shell Sort typically starts with a gap of half the list length, i.e., gap = n // 2.

2. Step 2: Understand gap reduction

   The gap is then reduced by half each iteration until it reaches 0.

3. Final Answer:

   gap = n // 2 -> Option C

4. Quick Check:

   Initial gap = n // 2 [OK]

Hint: Start gap at half the list length [OK]

Common Mistakes:

• Starting gap at 1 (too small)
• Starting gap equal to n (too large)
• Multiplying gap by 2 instead of dividing

3. What will be the output of the following Python code using Shell Sort?

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            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

arr = [9, 8, 3, 7, 5]
shell_sort(arr)
print(arr)

medium

A. [3, 7, 5, 8, 9]

B. [3, 5, 7, 8, 9]

C. [9, 8, 7, 5, 3]

D. [5, 3, 7, 8, 9]

Solution

1. Step 1: Trace the sorting process

   The code implements Shell Sort correctly. It sorts the list [9, 8, 3, 7, 5] into ascending order.

2. Step 2: Verify final sorted list

   After sorting, the list becomes [3, 5, 7, 8, 9].

3. Final Answer:

   [3, 5, 7, 8, 9] -> Option B

4. Quick Check:

   Sorted list = [3, 5, 7, 8, 9] [OK]

Hint: Shell Sort outputs sorted list in ascending order [OK]

Common Mistakes:

• Assuming original list remains unchanged
• Confusing descending with ascending order
• Misreading the gap reduction loop

4. Identify the error in this Shell Sort implementation:

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            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

medium

A. The inner while condition uses arr[j + gap] instead of arr[j - gap].

B. The gap is not reduced correctly in the loop.

C. The for loop range is incorrect; it should start from 0.

D. The temporary variable 'temp' is not assigned properly.

Solution

1. Step 1: Check the inner while loop condition

   The condition uses arr[j + gap] which is incorrect; it should compare arr[j - gap] to temp.

2. Step 2: Confirm correct element shifting

   Using arr[j + gap] can cause index errors or wrong comparisons; arr[j - gap] ensures proper backward comparison.

3. Final Answer:

   The inner while condition uses arr[j + gap] instead of arr[j - gap]. -> Option A

4. Quick Check:

   Compare with arr[j - gap], not arr[j + gap] [OK]

Hint: Check index directions carefully in inner loops [OK]

Common Mistakes:

• Using wrong index direction in comparisons
• Not reducing gap properly
• Incorrect loop start index

5. Given the list [23, 12, 1, 8, 34, 54, 2, 3], what will be the state of the list after the first gap iteration (gap = 4) in Shell Sort?

hard

A. [23, 12, 1, 3, 34, 54, 2, 8]

B. [3, 12, 1, 8, 2, 54, 23, 34]

C. [2, 12, 1, 8, 23, 54, 3, 34]

D. [23, 12, 1, 8, 34, 54, 2, 3]

Solution

1. Step 1: Identify elements compared with gap 4

   Elements compared are pairs 0 & 4, 1 & 5, 2 & 6, 3 & 7.

2. Step 2: Perform swaps if needed

   Compare and swap if left element > right element:
   Index 0 & 4: 23 > 34? No swap.
   Index 1 & 5: 12 > 54? No swap.
   Index 2 & 6: 1 > 2? No swap.
   Index 3 & 7: 8 > 3? Yes, swap 8 and 3.

3. Step 3: Result after first gap iteration

   The list becomes [23, 12, 1, 3, 34, 54, 2, 8].

4. Final Answer:

   [23, 12, 1, 3, 34, 54, 2, 8] -> Option A

5. Quick Check:

   After gap=4: [23, 12, 1, 3, 34, 54, 2, 8] [OK]

Hint: Check pairs separated by gap, swap if left > right [OK]

Common Mistakes:

• Not swapping elements correctly at gap distance
• Confusing final list after full sort with partial iteration
• Ignoring insertion steps within gap