Insertion sort builds the sorted array one value at a time, the way most people sort a hand of playing cards. It takes the next value as the key, then shifts every bigger value in the sorted part one place right until the key’s spot opens up. This visualizer shows the key in purple sliding left past bigger values, with the sorted part in green.
Try a nearly sorted input: each key only moves a step or two, so the whole sort takes almost linear time. That is why insertion sort beats quick sort and merge sort on small or almost-sorted arrays and is used inside hybrid sorts such as Timsort and introsort.
How to use the Insertion Sort Visualizer tool
- Pick an array size and an input: random, nearly sorted, reversed or few unique values. You can also type your own numbers.
- Press Play to watch the sort, or Step to move one comparison or swap at a time. Back goes one step back.
- Follow the colours: orange bars are being compared, red bars are being swapped or written, green bars are in their final place.
- Read the message under the controls and the highlighted pseudocode line to see exactly what the algorithm is doing.
- Change the speed, switch the code tab to C++, Java, Python or JavaScript, and compare the counters with other inputs.
Why use ToolOrca Insertion Sort Visualizer
- Animated bars with play, pause, step and step back
- Speed slider and a position slider to jump to any step
- Comparison and swap counters
- Random, nearly sorted, reversed and few-unique inputs, or your own numbers
- Highlighted pseudocode line for every step
- Code in C++, Java, Python and JavaScript
- Works on phones and tablets, keyboard accessible
How insertion sort works
For each i from 1 to n − 1, save key = a[i] and set j = i − 1. While j ≥ 0 and a[j] > key, copy a[j] to a[j + 1] and decrease j. When the loop stops, a[j + 1] is the key’s place: write it there. Positions 0 to i are now sorted. In the animation the shift is drawn as the key bar trading places with each bigger bar, which gives the same result.
Time and space complexity of insertion sort
The number of shifts equals the number of inversions (pairs that are out of order). A reversed array has n(n − 1)/2 inversions, so the worst and average cases are O(n²). An already sorted array has none: one comparison per value, O(n). More generally it runs in O(n + d) time where d is the number of inversions. It sorts in place with O(1) memory, is stable and is online: it can sort values as they arrive.
When to use insertion sort
Insertion sort is the best simple sort: use it for small arrays (up to about 16 to 32 values), for data that is already nearly sorted, and for adding a few new values to a sorted list. Python’s and Java’s Timsort and C++’s introsort switch to insertion sort for small pieces because its low overhead beats O(n log n) algorithms there.
Every visualizer on this site runs in your browser with the same controls: Play, Pause, Step forward, Step back and a speed slider. You can also drag the position slider to jump to any step, or focus the drawing and use the Space bar and arrow keys.
Frequently asked questions
What is the time complexity of insertion sort?
O(n²) on average and in the worst case (reversed input), and O(n) in the best case (already sorted).
Is insertion sort stable?
Yes. It only shifts values that are strictly greater than the key, so equal values keep their order.
Why is insertion sort fast on nearly sorted data?
Each value only moves past the values that are out of order with it. If there are few such inversions, there is very little shifting to do.
Is insertion sort better than bubble sort?
Yes, in practice. Both are O(n²), but insertion sort does fewer comparisons and writes on typical input and handles nearly sorted data better.
Where is insertion sort used in real libraries?
Inside hybrid algorithms: Timsort (Python, Java objects) and introsort (C++ std::sort) use insertion sort for small sub-arrays.