1. Initial gap
Start by comparing values far apart.
let gap = Math.floor(arr.length / 2)Typorithm · medium
Shell Sort
▷ Interactive algorithm labshell-sortsortinggapinsertion-sortin-place
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Shell Sort
Sorting Algorithms
Shell Sort is a gap-based upgrade to Insertion Sort that moves values long distances early.
Insertion Sort is fast when values are already near their final positions.
Shell Sort starts with a large gap so misplaced values can move across the array quickly.
Each gap pass performs insertion-style shifting inside gapped subsequences.
The gap shrinks until it reaches 1, where the final pass behaves like Insertion Sort on a nearly sorted array.
Runtime depends on the gap sequence; this simple halving sequence is easy to learn.
Preparing algorithm lab…
01
Start with a large gap.
02
Do insertion-style shifts by that gap.
03
Shrink the gap after each pass.
04
Final gap 1 cleans up the array.
05
In-place and usually faster than plain Insertion Sort.
function shellSort(arr) {
let gap = Math.floor(arr.length / 2);
while (gap > 0) {
for (let i = gap; i < arr.length; i++) {
const current = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > current) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = current;
}
gap = Math.floor(gap / 2);
}
return arr;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Gap loop
Repeat passes until the final gap of 1 is completed.
while (gap > 0)3. Gapped scan
Start at gap so j - gap is a valid earlier position.
for (let i = gap; i < arr.length; i++)4. Current value
Save the value before shifting gapped elements.
const current = arr[i]5. Moving index
j moves left by gap-sized jumps.
let j = i6. Gapped shift condition
Shift earlier gapped values while they are larger than current.
while (j >= gap && arr[j - gap] > current)7. Shift by gap
Move the larger gapped value right into j.
arr[j] = arr[j - gap]8. Jump left
Move to the previous value in the gapped subsequence.
j -= gap9. Shrink gap
Smaller gaps refine the order until gap 1 finishes with insertion-sort behavior.
gap = Math.floor(gap / 2)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.