Insertion sort: the idea
Prerequisites: Arrays, comparisons, and a sorted prefix.
Insertion sort starts with a prefix containing one item. For each next item, it swaps that item leftward while the preceding value is larger. When it reaches a smaller or equal value, or the beginning, its place is correct. The prefix has grown by one. This adjacent-swap implementation preserves the order of equal values.
Try it on the same input
Choose Nearly sorted and compare the swap count with Reversed. Small local disruptions need few swaps. Track equal items on Repeated values: the strict greater-than comparison keeps them in their original order.
Time, memory, and stability
n is the number of input items. Best O(n); average and worst O(n²). O(1) auxiliary space.
A stable sort preserves the original order of items whose values are equal. This implementation is stable. Identity labels record each item’s initial position. An unstable algorithm can preserve equal-item order on a particular input; it makes no guarantee for all inputs.
These bounds describe the sorting algorithm itself. The visualization saves a copy of the array at every operation for reversible playback, so recording uses additional time and memory. Its input size is capped at 24 items.
When to use it—and what to watch
Excellent for small or nearly sorted arrays, but a reversed large array requires a quadratic number of comparisons and swaps.
Reading the display
Comparisons count tests between item values. A swap writes two array positions; a merge write updates one. The counters exclude copying merge buffers, index tests, and playback work, so they are teaching measurements rather than elapsed-time benchmarks. Green marks final positions; a highlighted range indicates current work. For recursive algorithms, depth counts the active call levels.
Continue exploring
- Bubble sort — Compare neighbors and let large values travel to the right.
- Selection sort — Find the smallest remaining item and place it in the next slot.
- Merge sort — Sort two halves, then weave their values into one ordered sequence.
- Quicksort — Partition around a pivot, then sort the ranges on either side.