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.