Insertion sort
Take the next value and insert it into the sorted prefix. Move larger neighbors one position to the right until there is a place for the key.
Up to 24 values. Try duplicates or negative numbers.
Step 0 / 27: Original array. The first element starts the sorted prefix.
Array: [5, 2, 4, 2, 1]
Comparisons: 0 · Writes: 0
Green: sorted prefix. Purple: held value. Highlighted bars: current operation. Positions start at zero.
What stays sorted
Before each insertion, the processed prefix is sorted. The key is held outside the array, leaving one empty slot. Each shift moves that hole to the left; insertion fills it and extends the sorted prefix.
Why the sort is stable
Equal values are not shifted past each other: the condition uses > rather than >=. In [5, 2, 4, 2, 1], the first 2 remains before the second 2. AlgiViz keeps an original-index id for each item.
Complexity
- Already sorted input
- O(n)
- Average and worst case
- O(n²)
- Extra memory of the in-place algorithm
- O(1)
The visualizer keeps a complete history of states. Its memory is O(n × number of steps), up to O(n³) for this implementation. This is separate from the memory of the sorting algorithm.
JavaScript implementation
This wrapper copies the input before running the in-place sort, so the complete function additionally uses O(n) memory.
function insertionSort(values) {
const result = [...values];
for (let i = 1; i < result.length; i++) {
const key = result[i];
let j = i - 1;
while (j >= 0 && result[j] > key) {
result[j + 1] = result[j];
j--;
}
result[j + 1] = key;
}
return result;
}Video walkthrough
Built with AlgiViz
This website defines the insertion-sort algorithm. AlgiViz provides immutable array operations, the playback timeline and canvas rendering. Video recording is a separate CanvasTake package; export is not connected to this page yet.