Move it step by step
Sort [5, 2, 8, 1, 9, 3, 7, 4] from smallest to largest
- 50
- 21
- 82
- 13
- 94
- 35
- 76
- 47
- Taken-out value (box above)
- Comparing
- Shifted
- Inserted
- Empty
- Sorted range
- The number below each box is its index
Step 1 of 470 comparisons0 shifts
Sorting 8 values from smallest to largest. The first value alone counts as already sorted.
The pseudocode line currently running
- 1Increase i from 1 to n - 1, one step at a time
- 2key = a[i] (take it out)
- 3j = i - 1
- 4While j >= 0 and a[j] > key
- 5a[j + 1] = a[j] (shift right)
- 6j = j - 1
- 7a[j + 1] = key (drop into the gap)
Change the example
Try predicting
You're on step 1.
Which index is compared next?
What you'll learn
- The flow of taking out one value and inserting it into the sorted part on the left
- Why the number of comparisons and shifts changes a lot depending on the order of the input
Prerequisites
- Arrays and indices (numbering that starts at 0)
- for loops and while loops
- Comparing two values
How this sort works
Insertion sort takes values one at a time from the left and inserts each one into its correct spot in the already-sorted part on its left.
It is the same motion as sorting playing cards in your hand, one card at a time. An array that is nearly sorted already finishes quickly.
Steps, with an example
- 1Treat the single leftmost value as already sorted
- 2Take out the next value, leaving a gap where it was
- 3Compare with the value to the left of the gap, and shift it into the gap if it is bigger
- 4Stop once the left neighbor is less than or equal to the taken-out value, or the left end is reached, then drop the value into the gap
- 5Repeat taking out and inserting until the rightmost value is placed
| Taken-out value | Compares / shifts | Sorted so far |
|---|---|---|
| 2to index 0 | 1 / 1 | 2, 5 |
| 8to index 2 | 1 / 0 | 2, 5, 8 |
| 1to index 0 | 3 / 3 | 1, 2, 5, 8 |
| 9to index 4 | 1 / 0 | 1, 2, 5, 8, 9 |
| 3to index 2 | 4 / 3 | 1, 2, 3, 5, 8, 9 |
| 7to index 4 | 3 / 2 | 1, 2, 3, 5, 7, 8, 9 |
| 4to index 3 | 5 / 4 | 1, 2, 3, 4, 5, 7, 8, 9 |
Comparisons and time complexity
| Case | Comparisons | Complexity |
|---|---|---|
| Best case | n - 1 (already sorted) | O(n) |
| Average case | About n² ÷ 4 | O(n²) |
| Worst case | n(n - 1) ÷ 2 (reverse order) | O(n²) |
For 8 values in reverse order, that is 28 comparisons and 28 shifts. For an already-sorted array, it is just 7 comparisons and zero shifts.
When to use it
Good fit
- Small arrays with up to a few dozen elements
- An array that is already mostly sorted, with just a few values added
- When you need to keep the order of equal values (a stable sort)
Not a good fit
- Large arrays with thousands of elements or more (use merge sort or quicksort instead)
- An array close to reverse order (this is where the number of shifts is highest)
Code
Pseudocode
- 1Increase i from 1 to n - 1, one step at a time
- 2key = a[i] (take it out)
- 3j = i - 1
- 4While j >= 0 and a[j] > key
- 5a[j + 1] = a[j] (shift right)
- 6j = j - 1
- 7a[j + 1] = key (drop into the gap)
Working code
▶ Press “Run” to see the result here
Edit the Python or JavaScript and press “Run” to see the result right away. Java is read-only here.
FAQ
- What changes if I replace a[j] > key with a[j] >= key?
- Equal values now get shifted right too, so the order between equal values can be swapped. The final sorted order is still the same, but the sort is no longer stable.
- Is this faster than Python's sorted or JavaScript's sort?
- For large arrays, the language's built-in sort is much faster. That said, many built-in sorts switch to insertion sort internally for short segments.
- Why keep the taken-out value outside the array?
- Because shifting values right overwrites the spot it came from. Copying it into key first means it can still be placed back into the gap after the shifting is done.