Shell Sort Algorithm in DSA C++

Mental Model

Shell sort improves simple sorting by comparing elements far apart first, then gradually reducing the gap to sort closer elements.

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 to get a fully ordered shelf.

Array: [8, 5, 3, 7, 6, 2, 4, 1]
Gap = 4 -> Compare elements 4 apart
Indexes: 0    1    2    3    4    5    6    7
Values:  8 -> 5 -> 3 -> 7 -> 6 -> 2 -> 4 -> 1

Dry Run Walkthrough

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

Goal: Sort the array in ascending order using Shell sort by reducing gap and sorting subarrays.

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

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

Why: Swapped 8 and 6 because 6 < 8 to partially sort distant elements

Step 2: Continue gap = 4, compare and sort elements 4 apart

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

Why: Swapped 5 and 1 because 1 < 5 to improve order

Step 3: Reduce gap to 2, sort elements 2 apart using insertion sort

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

Why: Sorting closer elements to refine order

Step 4: Reduce gap to 1, final insertion sort pass

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

Why: Final pass to fully sort the array

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // gap reduces each iteration
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            // insertion sort for elements gap apart
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

int main() {
    vector<int> arr = {8, 5, 3, 7, 6, 2, 4, 1};
    shellSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

for (int gap = n / 2; gap > 0; gap /= 2) {

reduce gap size each iteration to sort elements closer together

for (int i = gap; i < n; i++) {

iterate over elements starting from gap index

while (j >= gap && arr[j - gap] > temp) {

shift elements greater than temp to the right to insert temp in correct position

arr[j] = temp;

insert temp at its correct sorted position within the gap-sorted subarray

Output

1 2 3 4 5 6 7 8 

Complexity Analysis

Time: O(n^(3/2)) on average because gap sequence reduces comparisons and shifts compared to simple insertion sort

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

vs Alternative: Faster than insertion sort (O(n^2)) for larger arrays by sorting distant elements first to reduce total shifts

Edge Cases

empty array

function returns immediately without changes

DSA C++

for (int gap = n / 2; gap > 0; gap /= 2) {

array with one element

array remains unchanged as it is already sorted

DSA C++

for (int gap = n / 2; gap > 0; gap /= 2) {

array with all elements equal

no swaps occur, array remains the same

DSA C++

while (j >= gap && arr[j - gap] > temp) {

When to Use This Pattern

When you need a faster version of insertion sort that works well on medium-sized arrays, use Shell sort because it reduces total shifts by sorting elements far apart first.

Common Mistakes

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

Mistake: Incorrectly shifting elements inside the inner while loop causing infinite loops
Fix: Ensure j is decremented by gap each time inside the while loop to move backwards properly

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 simple, in-place sorting faster than insertion sort for medium arrays.

The key insight is sorting distant elements first reduces the total work needed for final sorting.

Practice

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

easy

A. It sorts elements by building a binary heap.

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

C. It uses a divide and conquer approach like merge sort.

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

Solution

1. Step 1: Understand Shell Sort's approach

   Shell Sort starts by comparing elements far apart using a gap, not just neighbors.

2. Step 2: Gap reduction and sorting

   The gap reduces gradually until it becomes 1, performing insertion sort at each stage.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap-based sorting [OK]

Hint: Remember: Shell Sort uses gaps that shrink over time [OK]

Common Mistakes:

• Thinking Shell Sort only swaps adjacent elements
• Confusing Shell Sort with merge or heap sort
• Ignoring the gap reduction step

2. Which of the following is the correct way to initialize the gap in Shell Sort for an array of size n in C++?

easy

A. int gap = n / 2;

B. int gap = n * 2;

C. int gap = n + 1;

D. int gap = 1;

Solution

1. Step 1: Identify the common gap initialization

   Shell Sort commonly starts with gap as half the array size, i.e., n/2.

2. Step 2: Check other options

   Multiplying or adding to n is incorrect; starting at 1 skips the gap sorting steps.

3. Final Answer:

   int gap = n / 2; -> Option A

4. Quick Check:

   Gap starts at half array size [OK]

Hint: Gap usually starts at half the array length [OK]

Common Mistakes:

• Starting gap at 1 instead of n/2
• Using gap larger than array size
• Confusing gap initialization with loop counters

3. What will be the output array after applying Shell Sort on arr = {9, 8, 3, 7, 5, 6, 4, 1}?

medium

A. [1, 3, 4, 5, 6, 7, 8, 9]

B. [9, 8, 7, 6, 5, 4, 3, 1]

C. [1, 4, 3, 5, 6, 7, 8, 9]

D. [3, 1, 4, 5, 6, 7, 8, 9]

Solution

1. Step 1: Apply Shell Sort steps on the array

   Start with gap = 4 (8/2), sort elements 4 apart, then gap = 2, then gap = 1.

2. Step 2: Final sorted array

   After all gap reductions and sorting, the array becomes fully sorted: [1, 3, 4, 5, 6, 7, 8, 9].

3. Final Answer:

   [1, 3, 4, 5, 6, 7, 8, 9] -> Option A

4. Quick Check:

   Shell Sort fully sorts array ascending [OK]

Hint: Shell Sort outputs a fully sorted array ascending [OK]

Common Mistakes:

• Confusing partial sorted arrays as final output
• Reversing the array order
• Ignoring gap-based sorting steps

4. Identify the error in the following Shell Sort code snippet:

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

medium

A. The inner while loop condition should be j > gap, not j >= gap.

B. No error; the code correctly implements Shell Sort.

C. The gap should start from n, not n/2.

D. The gap update should be gap = gap - 1 instead of gap /= 2.

Solution

1. Step 1: Review gap initialization and update

   Gap starts at n/2 and halves each iteration, which is correct for Shell Sort.

2. Step 2: Check inner loop and conditions

   The while loop uses j >= gap to avoid out-of-bound and correctly shifts elements.

3. Final Answer:

   No error; the code correctly implements Shell Sort. -> Option B

4. Quick Check:

   Code matches Shell Sort logic [OK]

Hint: Check gap halving and while loop conditions carefully [OK]

Common Mistakes:

• Changing gap update to subtract 1 breaks algorithm
• Using incorrect while loop boundary causes errors
• Starting gap at n causes out-of-bound issues

5. Given an array arr = {23, 12, 1, 8, 34, 54, 2, 3}, how many times will the inner while loop execute during the first gap iteration (gap = 4) in Shell Sort?

hard

A. 5 times

B. 4 times

C. 3 times

D. 6 times

Solution

1. Step 1: Identify elements compared with gap = 4

   Pairs compared: (23, 34), (12, 54), (1, 2), (8, 3).

2. Step 2: Count while loop executions

   Only pairs where left element > right element cause shifts. Here, (23 > 34) no, (12 > 54) no, (1 > 2) no, (8 > 3) yes. For (8,3), shifting occurs once. Also, elements at indices 4 to 7 are checked, total 4 iterations of the outer loop, but only 1 inner while loop execution occurs.

3. Final Answer:

   3 times -> Option C

4. Quick Check:

   Count actual inner while loop executions, not just comparisons [OK]

Hint: Count pairs separated by gap and check conditions [OK]

Common Mistakes:

• Counting only swaps, not all while loop checks
• Ignoring elements beyond first gap iteration
• Misunderstanding gap-based comparisons