The Idea
Insertion Sort is how almost everyone sorts a hand of playing cards without thinking about it. You pick up cards one at a time and slide each new card into the right spot among the cards you've already arranged. The cards to the left of your current card are always sorted; the cards to the right haven't been touched yet. The algorithm grows a sorted prefix one element at a time, shifting larger neighbors over to make room for each new arrival.
How It Works
The array is mentally split into two regions: a sorted prefix on the left and an unsorted suffix on the right. Each pass picks the next unsorted element (the "key"), and shifts elements of the sorted prefix one slot to the right until the key's correct spot is uncovered. Then the key slides in.
The success-green slots are the sorted prefix — the part of the array you can rely on to be in order. Every pass extends that prefix by exactly one element.
The Algorithm
- Treat
arr[0]as a sorted prefix of length 1. - Loop
ifrom1toN - 1. The element atarr[i]is the "key". - Walk backwards from
i - 1, shifting elements one slot to the right while they're greater than the key. - When you hit a position whose value is
<= key(or you fall off the left edge), drop the key into the gap. - The sorted prefix is now one element longer. Continue until
i = N - 1.
Trace Through an Example
Running insertion sort on [5, 2, 4, 1, 3]:
| Step | Action | Array State |
|---|---|---|
| Start | prefix is just [5] | [5, 2, 4, 1, 3] |
| i = 1 | key = 2; shift 5 right, insert 2 at 0 | [2, 5, 4, 1, 3] |
| i = 2 | key = 4; shift 5 right, insert 4 at 1 | [2, 4, 5, 1, 3] |
| i = 3 | key = 1; shift 5, 4, 2 right, insert 1 at 0 | [1, 2, 4, 5, 3] |
| i = 4 | key = 3; shift 5, 4 right, insert 3 at 2 | [1, 2, 3, 4, 5] |
| Done | prefix is the whole array | [1, 2, 3, 4, 5] |
You can read the array left-to-right at any moment and the sorted region is always there in front of you.
Complexity
| Case | Time | Why |
|---|---|---|
| Best | O(N) | already sorted — the inner while loop never executes |
| Average | O(N²) | each key shifts roughly N/4 slots on average |
| Worst | O(N²) | reverse-sorted — every key shifts the entire prefix |
| Space | O(1) | in-place, only the key variable |
The headline number is the O(N) best case. For nearly-sorted arrays — where every element is at most a few slots from its correct position — insertion sort runs in nearly linear time. This is why it beats fancier O(N log N) sorts on small or nearly-sorted inputs.
When Should You Use It?
- Use it for small arrays (~10-50 elements). The low constant factor and tight inner loop beat merge sort and quick sort below that threshold.
- Use it when data arrives one element at a time and you need an "always sorted" buffer — streaming sensor readings, leaderboards, online algorithms.
- Don't use it as your only sort for general input. On large random arrays, the O(N²) shifts will crush you.
- The transferable pattern: insertion sort is the workhorse inside Tim Sort — the algorithm behind Python's
sorted()and Java'sArrays.sort()for objects. Tim Sort uses merge sort for the big picture and insertion sort for small runs, because that combination is genuinely the fastest thing we know on real-world data.