- Being inserted
- Compared
- Swapped
- Sorted part
Insertion sort
Insertion sort works the way many people sort playing cards in their hand. It keeps a sorted part at the front of the list, takes the next value, and slides it back past every larger value until it fits. Play the sort at any speed, or step through it one comparison at a time, and watch the counters for comparisons, swaps, and passes. Press Play to watch the sort, or Step and Back to go one comparison at a time. Drag the step slider to jump anywhere. The tiles count comparisons, swaps and passes. Choose how many bars, how they start, or type your own numbers. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Choose how many bars and how they start: random, nearly sorted, reversed, or with few unique values. Or type your own numbers.
- Press Play, or use Step and Back to move one comparison at a time. Drag the step slider to jump anywhere in the sort.
- Try a nearly sorted list and a reversed one, and compare how many comparisons each takes.
How insertion sort works
The first value on its own is a sorted part. Take the second value and compare it with the one before it; if that one is larger, swap them, and keep comparing and swapping until the value before is not larger or the value reaches the front. Now the first two values are in order. Do the same with the third value, the fourth, and so on to the end of the list.
Fast on nearly sorted lists
Each pass stops at the first value that is not larger, so a value that is already close to its place costs only a comparison or two. A sorted list takes n − 1 comparisons and no swaps; a reversed list, the worst case, takes n(n − 1)/2 of each. The number of swaps always equals the number of inversions in the start list, the pairs that are out of order. That is why insertion sort is often used for short or nearly sorted lists, and inside faster sorts to finish small pieces.
Frequently asked questions
How does insertion sort work?
It builds a sorted part at the front of the list. Each pass takes the next value and moves it back past every larger value before it, until it fits. After pass k the first k + 1 values are in order, though a later value can still be inserted between them.
How many comparisons and swaps does insertion sort make?
The swaps always equal the number of inversions in the start list: none for a sorted list, n(n − 1)/2 for a reversed one. The comparisons are the swaps plus at most one per pass, so between n − 1 and n(n − 1)/2.
Why is insertion sort fast on nearly sorted lists?
Because a pass stops as soon as it meets a value that is not larger. When every value is close to its final place, each pass is short, and the whole sort takes time close to n.
Is insertion sort stable?
Yes. A value only moves past values that are strictly larger, so equal values never pass each other and keep their original order.
Are my numbers sent anywhere?
No. The sort runs in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor