Shell Sort

A generalization of insertion sort that allows swapping of elements that are far apart. It starts with large gaps between compared elements and progressively reduces the gap.

Algorithm Information

Time Complexity

Best: O(n log n)
Average: O(n^1.5)
Worst: O(n²)

Space Complexity

O(1)

Properties

• Unstable sorting algorithm
• In-place sorting
• Gap-based insertion sort
• Adaptive
1/48
Speed: 1x

Algorithm Code

1function shellSort(arr) {
2  const n = arr.length;
3 
4  // Start with a big gap, then reduce
5  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
6 
7    // Gapped insertion sort for this gap size
8    for (let i = gap; i < n; i++) {
9      const temp = arr[i];
10      let j = i;
11 
12      // Shift elements that are gap apart
13      while (j >= gap && arr[j - gap] > temp) {
14        arr[j] = arr[j - gap];
15        j -= gap;
16      }
17 
18      // Place temp at correct position
19      arr[j] = temp;
20    }
21  }
22 
23  return arr;
24}

Variable State

i:0
j:0
n:7
gap:3
temp:0

Call Stack

shellSort

Array Visualization

Watch how Shell Sort processes the array step by step

64
0
34
1
25
2
12
3
22
4
11
5
90
6

Statistics

Comparisons0
Swaps0
Step1 / 48

Legend

Comparing
Active / Swapping
Sorted
Unsorted

Starting Shell Sort algorithm

How Shell Sort Works

Learn the fundamentals of shell sort through step-by-step explanations, code examples, and key concepts.