Shell Sort vs Insertion Sort
Same 110 values, same shuffle, same speed. Shell Sort finishes first and turns gold: 1,910 operations to 5,689.
The numbers
- Shell operations
- 1,910
- Insertion operations
- 5,689
- Shell average
- n^1.5
- Insertion average
- n²
- Shell worst
- n²
- Insertion worst
- n²
Shell Sort
Shell Sort runs insertion sort on elements far apart first, then on closer and closer elements. More on Shell Sort.
Insertion Sort
Insertion Sort takes each value in turn and slides it left until it sits in the right place. More on Insertion Sort.
FAQ
Which is faster, Shell Sort or Insertion Sort?
On this shuffle of 110 values, Shell Sort needed 1,910 operations and Insertion Sort needed 5,689, about 3.0× as many. On average Shell Sort is n^1.5 and Insertion Sort is n².
Which one is stable?
Insertion Sort is stable; Shell Sort is not.
How is the race fair?
Both algorithms start from the same shuffle and run the same number of operations per frame. Every comparison, swap and write counts as one operation, so the one that needs fewer operations finishes first.