Interactive demo
Insertion Sort Visualization
Insertion sort works like sorting playing cards in your hand: it takes one element after the other and inserts it into the sorted part at the right place. It is very fast on nearly sorted arrays.
Try “Nearly sorted”: only a few elements have to move. “Reversed” is the worst case.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Unsorted element
- Sorted part
- Element being inserted
- Compared element
- Final position
Runtime and properties
Best case
O(n)
Already sorted: every element only needs one comparison to stay where it is.
Average case
O(n²)
On average every element shifts past half of the sorted part.
Worst case
O(n²)
Reversed order: every element has to shift past the whole sorted part.
Extra memory
O(1)
Only the element being inserted is held aside.
Stable
Yes
Elements shift only past larger ones, never past equal ones.
In-place
Yes
Elements are shifted within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort this page | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Take an element out
The sorted part starts with the first element. The next element is taken out, which leaves a gap in the array.
2. Shift larger elements
Going left through the sorted part, every larger element is shifted one place to the right into the gap. The gap moves left with it.
3. Insert
At the first element that is not larger, the taken element drops into the gap. On nearly sorted arrays this happens almost immediately, which is why many fast sorting algorithms use insertion sort for small parts.