Watch insertion sort take each element and slide it left into the sorted region — like sorting cards in your hand. See why it is near O(n) on almost-sorted data.
Algorithm
Array
Comparisons
0
Swaps/writes
0
Step
0/1,373
Reads
0
Aux memory
0
Call depth
1/1
Slow the speed and use Step to match the pseudocode highlight with the bar colors.
Pseudocode
for i ← 1 to n−1
key ← a[i], j ← i−1
while j ≥ 0 and a[j] > key
a[j+1] ← a[j], j ← j−1
a[j+1] ← key
Time complexity
| Best | O(n) |
|---|---|
| Average | O(n²) |
| Worst | O(n²) |
| Space | O(1) |
| Stable | Yes |
Insertion sort picks up each element (the key) and shifts larger elements one slot right until the key fits — exactly how most people sort playing cards.
Worst case is O(n²), but on nearly-sorted data each element moves only a few slots, making it effectively O(n). That is why real hybrid sorts (Timsort, Introsort) switch to insertion sort on short runs. Stable and in-place. Sorting Visualizer