B-TIER technique
Shell sort — gap-based insertion sort that moves items far early
100k ft — What is this?
Shell sort — gap-based insertion sort that moves items far early
50k ft — Why care?
Shell sort runs insertion sort on elements separated by a shrinking gap, letting small values travel long distances early. By the final gap-1 pass the list is nearly sorted, so insertion sort finishes quickly.
10k ft — Key takeaways
• Final pass with gap 1 is cheap on nearly sorted data
• Gapped passes fix insertion sort's one-step-at-a-time weakness
5k ft — Tools & techniques
(no tools tagged)
insertion sort, shell sort
1k ft — Deep-dive / try it
Shell sort solves insertion sort’s biggest problem #code #algorithms
Transcript excerpt
Shell Sort is an optimized version of Insertion Sort, and what makes it faster is a pretty clever change. Insertion Sort works by scanning the list, comparing each number to the one before it. If it's smaller, it slides backwards until it hits a number smaller than itself. But when a small number starts near the end of the list, it can only move back one step at a time, which makes Insertion Sort slow on large unsorted arrays. Shell Sort fixes this by comparing numbers that are separated by a gap. It runs Insertion Sort on these spaced-out subsequences, allowing small numbers to move large distances across the list much earlier. The gap is reduced with each pass until it reaches one. By then, the list is already mostly sorted, so a final Insertion Sort pass quickly finishes the job. So by introducing gaps...