How Shell Sort Works
- Waiting
- Being compared
- Just moved
- In final position
1/88
Shell sort, 12 values in random order.
Settings
More options
Starting order
Two to 48 numbers, used in the order you type them.
Shell Sort
- 1
gap = n / 2 - 2
while gap >= 1: - 3
for i in gap..n-1: - 4
key = a[i]; j = i - 5
while j >= gap and a[j-gap] > key: - 6
a[j] = a[j-gap] - 7
j -= gap - 8
a[j] = key - 9
gap = gap / 2
How the Seven Compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Scroll the table sideways for the rest of the columns.
Stable means equal values keep their original order.