How insertion sort works
- The first value on its own is a sorted part of length one.
- Take the next value as the key.
- Compare the key with the value on its left. While the key is smaller, the two change places.
- Stop when the value on the left is not greater, or when the key reaches the start. The sorted part is now one value longer.
What the colours mean
Black is the key, the value being placed. Yellow is the value compared with it, and pink is the value that just moved one place right. Pale green bars are in order among themselves but can still move when a smaller key arrives. They turn full green at the end.
Insertion Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n) | O(n²) | O(n²) | O(1) | Yes |
On a sorted array each key needs one comparison and nothing moves: 9 comparisons and 0 writes for 10 values. On a reversed array every key travels all the way to the front, which takes 45 comparisons. Choose Nearly sorted to see why insertion sort is the usual pick for small or almost ordered data.
The method shown writes the key back after every shift, so each move counts as two writes. The recursive version in the article holds the key aside and writes it once, when its place is found.
The C# code
The listing beside the bars is the iterative SortArray() method from Insertion Sort in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is insertion sort stable?
Yes. The key moves left only past values that are strictly greater, so it stops behind an equal value.
Why is insertion sort fast on nearly sorted data?
Each key travels only as far as it is out of place. If every value is a few positions from where it belongs, each key needs a few comparisons, and the total grows in step with the array size.
Is insertion sort used in real libraries?
Yes. Array.Sort in .NET uses introsort, which hands partitions of 16 or fewer elements to insertion sort.