Insertion Sort

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

Size48
ComparingSwap/writePivot/keyReadSorted
Speed50×

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

BestO(n)
AverageO(n²)
WorstO(n²)
SpaceO(1)
StableYes

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

Frequently asked questions

When is insertion sort fast?
On small arrays (roughly under 50 elements) or nearly-sorted data — fast enough that production hybrid sorts use it for short partitions.
Is insertion sort stable?
Yes — only strictly larger elements are shifted, so equal keys keep their order.

Other algorithms