Shell Sort Algorithm in DSA Javascript

Mental Model

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

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 neat order.

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 helps move bigger elements towards the end early

Step 2: Reduce gap to 2, compare and sort elements 2 apart

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

Why: Smaller gap refines the order by sorting closer elements

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

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

Why: Gap 1 means sorting every element with its neighbor to finalize order

Result:

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

Annotated Code

DSA Javascript

class ShellSort {
  static sort(arr) {
    let n = arr.length;
    // Start with a big gap, then reduce it
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
      // Do a gapped insertion sort for this gap size
      for (let i = gap; i < n; i++) {
        let temp = arr[i];
        let 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;
      }
    }
    return arr;
  }
}

// Driver code
const array = [8, 5, 3, 7, 6, 2, 4, 1];
const sortedArray = ShellSort.sort(array);
console.log(sortedArray.join(", "));

for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {

reduce gap size step by step to refine sorting

for (let 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 to the right within gap distance

arr[j] = temp;

insert temp in its correct position for current gap

Output

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

Complexity Analysis

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

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

vs Alternative: Shell sort is faster than simple insertion sort for larger arrays because it moves elements farther apart early, reducing total shifts

Edge Cases

empty array

returns empty array immediately without errors

DSA Javascript

for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {

array with one element

returns the same single-element array as sorted

DSA Javascript

for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {

array with duplicate elements

duplicates are kept and sorted correctly in order

DSA Javascript

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

When to Use This Pattern

When you see a problem asking to sort efficiently without extra space and with better performance than insertion sort, consider Shell Sort because it uses gap-based insertion to speed up sorting.

Common Mistakes

Mistake: Not reducing the gap correctly, causing infinite loops or incorrect sorting
Fix: Ensure gap is updated by dividing by 2 each iteration until it reaches zero

Mistake: Using gap = 1 from the start, which reduces Shell Sort to simple insertion sort
Fix: Start with gap as half the array length and reduce gradually

Mistake: Not shifting elements correctly inside the while loop, leading to wrong order
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 sort the entire array.

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

The key insight is that sorting elements far apart first moves items closer to their final position, reducing total shifts later.

Practice

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

easy

A. It builds a heap and extracts the maximum element repeatedly.

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

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

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

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 merge sort or heap sort, Shell Sort uses gap-based comparisons, not divide and conquer or heap structure.

3. Final Answer:

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

4. Quick Check:

   Shell Sort = gap-based comparisons [OK]

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

Common Mistakes:

• Confusing Shell Sort with merge sort or quicksort
• Thinking it only swaps adjacent elements like bubble sort
• Assuming it uses a heap structure

2. Which of the following is the correct syntax to start the gap value in a Shell Sort implementation in JavaScript?

easy

A. let gap = Math.floor(array.length / 2);

B. let gap = array.length * 2;

C. let gap = 0;

D. let gap = array.length + 1;

Solution

1. Step 1: Identify typical gap initialization

   Shell Sort usually starts with gap as half the array length, using Math.floor for integer division.

2. Step 2: Check each option

   let gap = Math.floor(array.length / 2); correctly sets gap to half length; others set invalid or zero gaps.

3. Final Answer:

   let gap = Math.floor(array.length / 2); -> Option A

4. Quick Check:

   Gap starts at half array length [OK]

Hint: Start gap as half array length using Math.floor [OK]

Common Mistakes:

• Setting gap to zero initially
• Using gap larger than array length
• Not using Math.floor for integer gap

3. What will be the output array after applying one full pass of Shell Sort with initial gap = 3 on the array [9, 8, 3, 7, 5, 6, 4, 1]?

medium

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

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

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

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

Solution

1. Step 1: Identify elements compared with gap 3

   Elements compared are at indices (0,3,6) and (1,4,7) and (2,5). For example, 9 and 7 and 4; 8 and 5 and 1; 3 and 6.

2. Step 2: Perform insertion sort on these groups

   Sorting group (9,7,4) gives (4,7,9), (8,5,1) gives (1,5,8), (3,6) stays (3,6). After rearranging, array becomes [4,1,3,7,5,6,9,8].

3. Final Answer:

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

4. Quick Check:

   Gap 3 pass sorts distant elements [OK]

Hint: Group elements by gap and sort each group [OK]

Common Mistakes:

• Not grouping elements by gap correctly
• Sorting entire array instead of gap groups
• Confusing indices during swaps

4. Identify the error in this Shell Sort snippet and choose the correct fix:

function shellSort(arr) {
  let gap = Math.floor(arr.length / 2);
  while (gap > 0) {
    for (let i = gap; i < arr.length; i++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = gap / 2;
  }
  return arr;
}

medium

A. Change while (gap > 0) to while (gap >= 0)

B. Change gap = gap / 2; to gap = Math.floor(gap / 2);

C. Change let j = i; to let j = gap;

D. Remove the inner while loop

Solution

1. Step 1: Analyze gap update

   The gap must be an integer; dividing by 2 without floor makes it a float, causing infinite loop.

2. Step 2: Fix gap update

   Using Math.floor ensures gap reduces properly and loop ends.

3. Final Answer:

   Change gap = gap / 2; to gap = Math.floor(gap / 2); -> Option B

4. Quick Check:

   Gap must be integer to avoid infinite loop [OK]

Hint: Always floor gap after division to keep it integer [OK]

Common Mistakes:

• Not flooring gap, causing infinite loop
• Changing loop conditions incorrectly
• Removing necessary inner loops

5. Given the array [23, 12, 1, 8, 34, 54, 2, 3], what will be the final sorted array after applying Shell Sort with gap sequence halving each time starting from Math.floor(length/2)?

hard

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

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

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

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

Solution

1. Step 1: Calculate initial gap and perform passes

   Initial gap = 4. After sorting groups with gap 4, array partially sorted. Then gap = 2, then gap = 1 (final insertion sort).

2. Step 2: Final sorted array after all passes

   After all gap passes, array becomes fully sorted ascending: [1, 2, 3, 8, 12, 23, 34, 54].

3. Final Answer:

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

4. Quick Check:

   Shell Sort fully sorts array ascending [OK]

Hint: Shell Sort ends with gap 1 insertion sort for full sorting [OK]

Common Mistakes:

• Stopping before gap reaches 1
• Misordering elements in final pass
• Confusing descending with ascending order