Shell Sort Algorithm in DSA Java

Mental Model

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

Analogy: Imagine organizing books on a shelf by first sorting every 3rd book, then every 2nd, and finally every book in order, making the final sorting easier.

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

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 disorder 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: Closer elements are sorted to prepare for final pass

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 Java

public class ShellSort {
    // Function to perform shell sort on array
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // Start with a big gap, then reduce it
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // Do a gapped insertion sort for this gap size
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                // Shift earlier gap-sorted elements up until the correct location for arr[i] is found
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // Put temp (the original arr[i]) in its correct location
                arr[j] = temp;
            }
        }
    }

    // Driver code to test shell sort
    public static void main(String[] args) {
        int[] arr = {8, 5, 3, 7, 6, 2, 4, 1};
        shellSort(arr);
        // Print sorted array
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

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 to end

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

shift elements greater than temp up by gap to make space

arr[j] = temp;

insert temp in correct position within 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 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 large arrays by reducing total shifts early

Edge Cases

empty array

function completes immediately without errors

DSA Java

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

array with one element

array remains unchanged, sorted trivially

DSA Java

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

array with all elements equal

no swaps occur, array remains unchanged

DSA Java

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

When to Use This Pattern

When you see sorting problems where insertion sort is too slow, try Shell sort by sorting elements far apart first to reduce disorder quickly.

Common Mistakes

Mistake: Not reducing the gap correctly (e.g., gap /= 2 missing or wrong)
Fix: Ensure gap is divided by 2 each outer loop iteration to progressively sort closer elements

Mistake: Incorrectly shifting elements inside the inner while loop causing index errors
Fix: Check that j >= gap before accessing arr[j - gap] to avoid out-of-bounds

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 and makes final sorting easier.

Practice

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

easy

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

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

C. It uses a divide and conquer approach to sort subarrays independently.

D. It builds a sorted list 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 options with concept

   It sorts elements by comparing distant elements and gradually reducing the gap. correctly describes this gap reduction and distant element comparison. Others describe different sorting methods.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap reduction and distant comparisons [OK]

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

Common Mistakes:

• Confusing Shell Sort with Bubble Sort
• Thinking it only swaps adjacent elements
• Mixing it up with Merge Sort or Insertion Sort

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

easy

A. int gap = arr.length / 2;

B. int gap = arr.length * 2;

C. int gap = arr.length + 1;

D. int gap = 0;

Solution

1. Step 1: Understand gap initialization

   Shell Sort starts with a gap usually half the array length to compare distant elements.

2. Step 2: Check options for correct initialization

   int gap = arr.length / 2; correctly sets gap to half the array length. Others are incorrect or ineffective.

3. Final Answer:

   int gap = arr.length / 2; -> Option A

4. Quick Check:

   Gap starts at half array length [OK]

Hint: Start gap at half array length for Shell Sort [OK]

Common Mistakes:

• Setting gap larger than array length
• Starting gap at zero causing no sorting
• Using gap as array length plus one

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

medium

A. [3, 1, 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. [1, 3, 4, 5, 6, 7, 8, 9]

Solution

1. Step 1: Apply Shell Sort on given array

   Start with gap = 4 (8/2), compare and swap distant elements, then reduce gap to 2, then 1, sorting progressively.

2. Step 2: Final sorted array

   After all gap reductions and swaps, 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 D

4. Quick Check:

   Shell Sort fully sorts array ascending [OK]

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

Common Mistakes:

• Confusing partial sorted states as final output
• Ignoring gap reductions
• Assuming reverse order output

4. Identify the error in this Shell Sort snippet:

for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  for (int i = gap; i < arr.length; 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 gap update should be gap = gap / 3, not gap /= 2.

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

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

D. The variable temp should be declared outside the loops.

Solution

1. Step 1: Analyze the loop and conditions

   The gap starts at half array length and halves each iteration, which is a common Shell Sort approach.

2. Step 2: Check inner loop and assignments

   The inner while loop correctly shifts elements greater than temp, and temp is assigned properly after shifting.

3. Final Answer:

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

4. Quick Check:

   Code matches standard Shell Sort logic [OK]

Hint: Check loop conditions and assignments carefully [OK]

Common Mistakes:

• Changing gap update incorrectly
• Misusing loop conditions causing index errors
• Declaring variables in wrong scope

5. Given an array int[] arr = {20, 35, -15, 7, 55, 1, -22};, how many times will the inner while loop execute during the first gap iteration in Shell Sort?

hard

A. 5 times

B. 3 times

C. 7 times

D. 9 times

Solution

1. Step 1: Determine initial gap

   Array length 7, gap = 3. Process i from 3 to 6.

2. Step 2: Count inner while loop executions (shifts)

   Initial: [20,35,-15,7,55,1,-22]
   - i=3, temp=7 vs arr[0]=20: 1 shift -> [7,35,-15,20,55,1,-22]
   - i=4, temp=55 vs arr[1]=35: 0 shifts (35 < 55)
   - i=5, temp=1 vs arr[2]=-15: 0 shifts (-15 < 1)
   - i=6, temp=-22 vs arr[3]=20 then arr[0]=7: 2 shifts
   Total: 1+0+0+2 = 3.

3. Final Answer:

   3 times -> Option B

4. Quick Check:

   Shifts first gap = 3 [OK]

Hint: Count shifts for each gap iteration carefully [OK]

Common Mistakes:

• Counting only comparisons, not shifts
• Ignoring multiple shifts per element
• Miscalculating gap or indices