Insertion Sort Visualization

Insertion Sort takes each value in turn and slides it left until it sits in the right place.

How it works

Insertion Sort builds the sorted list one value at a time, the way many people sort a hand of cards. Each new value is compared with the sorted values to its left and shifted past every larger one until it reaches its place.

On random data each value travels about halfway back, so the total work is about n²/4 comparisons, which makes it slow for big lists. But it is very fast on data that is already nearly sorted (close to n), it is stable, it sorts in place, and its loop is tiny. That is why hybrid sorts like Tim Sort use it for short runs.

What to watch for

Watch a sorted rainbow grow from the left edge while each new value slides backwards into it.

Complexity

Best

n

Average

n²

Worst

n²

Extra space

1

Stable

Yes

Race it

Same shuffle, same speed, one winner: Insertion vs Bubble. Or open the studio to try other layouts, sizes and speeds, and make a video of it.

FAQ