Insertion Sort

Sorting and Searching · 20 min

DSA · Sorting

Insertion sort, one card at a time

Lift the next value out, slide the bigger ones right, drop it into the gap. Stable, in place, and the fastest simple sort on nearly sorted data.

Step through 5 1 4 2 — shift vs swap →
5 1 4 2 · unsorted
→
1 2 4 5 · sorted

01 The idea

You already know this one — it is how you sort a hand of cards

Pick up a hand of playing cards one at a time. The cards already in your hand are in order. When a new card arrives you run your eye leftwards along the hand, find the spot where it fits, push the bigger cards a little to the right, and slot it in. You never look at the cards further left, because they are already smaller than the one that stopped you.

Insertion sort does exactly that to an array. It keeps a sorted prefix at the front and grows it by one slot per round. The value sitting at the boundary is lifted out into a variable, the bigger values in the prefix slide one place right to open a gap, and the lifted value drops into that gap. After n-1 rounds the prefix is the whole array.

The important word is slide. Most people write this with swaps the first time, because bubble sort taught them to swap. Swapping sorts correctly, but it pays two array writes for every one place a value moves. Section 03 puts the two versions side by side and counts.

Take the next value out of the array and hold it. Slide every bigger value in the sorted part one place right, then drop your value into the gap that opens up.
Sorted prefixThe first few slots, already in order among themselves. It starts as slot 0 alone and grows by one slot every round.
KeyThe single value lifted out of the array and parked in a variable. Its old slot becomes a gap for the sliding values to fill.
ShiftCopying one value one slot to the right. It costs one array write. A swap costs two, because it writes both cells.

02 Hand trace

Sorting 5 1 4 2 by hand

Four values, three rounds. Slot 0 counts as a sorted prefix of one, so round 1 starts at slot 1. Follow 5 as you read down: it never jumps, it only ever slides one slot right at a time. A dot marks the gap — the slot whose value is currently being held in the key variable.

key = 15·425 > 1, so 5 slides right
insert 11542the scan ran off the left edge · prefix 1 5
key = 415·25 > 4 so 5 slides; then 1 is not bigger, so the scan stops
insert 41452prefix 1 4 5
key = 2145·5 slides, then 4 slides; then 1 stops the scan
result1245sorted · 6 comparisons · 4 slides · 7 writes

Count the work. Round 1 made 1 comparison, round 2 made 2, round 3 made 3, so 6 comparisons in total. Four slides happened — 5 slid three times and 4 slid once — and three keys were dropped into gaps, which is 4 + 3 = 7 array writes. Be honest about what this list costs: round i can never make more than i comparisons, so 6 is the most four values can possibly cost. 5 1 4 2 is a worst case for comparisons.

Look at where each scan stopped, though. Rounds 2 and 3 both halted on the 1 in slot 0 instead of running off the left edge. On this list that saved nothing, because slot 0 was the last slot either way — but the rule that stopped them is the one that matters. The instant a value is not bigger than the key, everything further left is smaller than it and therefore smaller than the key, so there is nothing left to check. On data that is already close to sorted the scans halt near the right-hand end and most of the prefix is never touched: 1 2 4 3 5 costs 5 comparisons and 1 slide, where the maximum for five values is 10 of each. That early exit is the thing the code in section 03 has to encode.

03 Mechanics

Swap every step, or lift the key and slide

Both versions sort correctly and both make exactly the same comparisons on any input. They differ only in how they move data. The left one drags a value leftwards by swapping it with its neighbour over and over. The right one takes the value out of the array first, so each move costs a single copy.

Naive · swap every step

for i = 1 to n-1:    j = i    while j > 0 and A[j-1] > A[j]:        swap A[j-1], A[j]  // 2 writes        j = j - 1

Improved · lift the key and shift

for i = 1 to n-1:    key = A[i]        // lift it out    j = i - 1    while j >= 0 and A[j] > key:        A[j+1] = A[j]  // 1 write        j = j - 1    A[j+1] = key    // fill the gap

Why lift the key out first. Once key holds a private copy, slot i is free, so a value can be copied rightwards without saving whatever it lands on. That turns every one-place move from two writes into one. On 5 1 4 2 the totals are 7 writes against 8; on the reversed list 5 4 3 2 1 they are 14 against 20.

Why the scan is allowed to stop early. while j >= 0 and A[j] > key exits the instant it meets a value that is not bigger. The prefix is sorted, so everything further left is smaller than that value and therefore smaller than the key too. In the trace, rounds 2 and 3 both halted on the 1 in slot 0 — which on that particular list saves nothing, since slot 0 ended the scan anyway. Load the nearly sorted preset 1 2 4 3 5 in section 04 to watch it actually pay: 5 comparisons and 1 slide, against a maximum of 10 of each for five values.

Why the test is > and never >=. A value equal to the key stops the scan, so the key lands to its right. Equal values therefore never cross each other and keep their input order. Changing that one character to >= makes insertion sort unstable and adds shifts that buy nothing.

05 Cheat sheet

The numbers to have ready

CaseTimeWhat the array looks like, and the exact count
Best — already sortedO(n)The inner test fails on its first try every round: n−1 comparisons and zero slides.
Average — random orderO(n²)Each key travels about half the prefix: roughly n²/4 comparisons and n²/4 slides.
Worst — reverse sortedO(n²)Every key travels the whole prefix: n(n−1)/2 comparisons and the same number of slides. For n = 5 that is 10 and 10.
Extra spaceO(1)One variable for the key and one index. It sorts inside the original array.
StableThe scan test is A[j] > key, strictly greater, so equal values never move past each other and tied records keep their input order.
AdaptiveThe number of slides equals the number of inversions in the input, so a run costs Θ(n + inversions). 5 1 4 2 has 4 inversions and the trace made 4 slides.
In place and onlineOne extra variable, no second array. It also works on a stream: each value can be inserted the moment it arrives, before the rest of the input is known.

06 Where & why

When insertion sort is the right answer

Insertion sort is not a fast sort. Its value is that it is the cheapest thing to run when the data is already close to sorted, and the cheapest thing to run when there is very little data. Both of those situations turn up constantly inside faster algorithms, which is why this quadratic sort is still shipping in every standard library.

Reach for it when…

The list is nearly sortedEach value moves a slot or two, so the run costs close to O(n). Selection sort pays n(n−1)/2 comparisons whatever the input, and bubble sort needs a whole extra pass over the array for every single slot a stray value has to move left.
The list is tinyBelow roughly 16 to 32 elements the low constant factor beats an O(n log n) sort once you count its recursion and index arithmetic.
Values arrive one at a timeYou can insert each new value into the sorted part as it appears, without waiting to see the rest of the input.
You need stability with no extra memoryMerge sort is stable but needs O(n) scratch space; heap sort is in place but not stable. Insertion sort is both.

Use something else when…

SituationBetter choiceWhy
The list is large and in random orderTimsort or introsort — the built-in sortAt n = 10,000 an O(n log n) sort does around 1.3 × 10⁵ comparisons; insertion sort averages around 2.5 × 10⁷.
Writes are the expensive operation, as on flash or EEPROMSelection sortIt performs at most n−1 swaps in total, while insertion sort can perform O(n²) writes.
You must guarantee O(n log n) in the worst case with O(1) spaceHeap sortNo quadratic worst case and no second array, at the cost of stability and cache friendliness.
The data is huge but arrives in long sorted runsTimsortIt detects those runs and merges them, and it uses binary insertion sort internally on the short pieces.
In a real project you will call the built-in sort. On most platforms that built-in contains insertion sort for the small pieces, so knowing exactly when it wins is the part an interview is testing.

07 Interview questions

Asked the way an interviewer asks them

Tap a question, say your answer out loud, then check it. Each answer is about twenty seconds of speech, which is the length an interviewer actually wants.

What is insertion sort, in one sentence?
You grow a sorted prefix one value at a time: lift the next value out, slide every bigger value in the prefix one slot right, and drop the value into the gap. It is how people sort a hand of cards. After round i the first i+1 slots are sorted among themselves, though they are not necessarily in their final positions.
What are the best, average and worst case time complexities?
Best is O(n) on an already sorted list, average is O(n²), and worst is O(n²) on a reverse sorted list. The worst case does exactly n(n−1)/2 comparisons and the same number of slides. Extra space is O(1) either way.
Why is the best case O(n) and not O(n²)?
Because the inner loop tests A[j] > key before it does anything, and on a sorted list that test fails immediately every round. Each round then costs one comparison and zero slides, so n−1 rounds cost n−1 comparisons. The outer loop still runs n−1 times, and that is where the n comes from.
Is insertion sort stable? Prove it.
Yes. The scan stops on A[j] > key, strictly greater, so a value equal to the key ends the scan and the key is dropped to its right. An equal value therefore never crosses another equal value, and records that tie on the sort field come out in input order. Change that > to >= and it stops being stable.
What does adaptive mean here, and exactly how adaptive is it?
Adaptive means the running time falls when the input is already partly ordered. For insertion sort the number of slides equals the number of inversions in the input, so the total cost is Θ(n + inversions). The list 5 1 4 2 has 4 inversions and the trace performs exactly 4 slides.
Why shift instead of swap?
A swap writes two array cells; a shift writes one, because the key is parked in a variable and its old slot is free to overwrite. On the reversed list 5 4 3 2 1 the shifting version does 14 array writes and the swapping version does 20. Both make the same 10 comparisons, so the entire saving is in data movement.
Does the shifting version always do fewer writes than the swapping one?
No, and this is the honest answer. It always pays one write to drop the key back even when nothing moved, so on an already sorted list of n values it does n−1 writes while the swapping version does zero. It wins whenever elements actually move, which covers the average and the worst case, and those are what the constant factor gets judged on.
Insertion sort versus bubble sort versus selection sort — which do you pick?
Insertion sort, almost always. Selection sort makes n(n−1)/2 comparisons on every input, sorted or not. Bubble sort with an early exit flag does get down to O(n) on an already sorted list, but its cost is set by how far the furthest value has to travel left: every single slot it moves costs another full pass over the array. Insertion sort is the only one of the three whose inner loop stops the instant it meets a smaller value, so it is the only one whose cost tracks the inversion count, Θ(n + inversions), rather than a count of passes.
Can you find the insertion point faster than a linear scan?
Yes, binary search the sorted prefix instead of walking it. That is binary insertion sort, and it drops comparisons to O(n log n). Total time stays O(n²) though, because the shifting is untouched, so it only pays off when a single comparison is expensive — long strings or a custom comparator.
How many comparisons does it make on 5 1 4 2, and how many writes?
Six comparisons: one in round 1, two in round 2 and three in round 3. That is the maximum possible for four values, because round i can compare at most i times. It also does 4 slides and 3 key placements, so 7 array writes in total.
State the loop invariant you would give in an interview.
Before round i, the sub-array A[0..i−1] holds the first i input values in sorted order. Each round preserves it by inserting A[i] into that sorted block, so when the loop ends at i = n the whole array is sorted. Initialisation, maintenance and termination — that is the standard proof.
Where is insertion sort actually used in production?
Inside faster sorts, essentially never on its own. Timsort, which Python and Java use for objects, builds its initial runs with binary insertion sort, and introsort and pdqsort in C++ fall back to insertion sort once a partition drops below roughly 16 elements. On a large unsorted array you would call the built-in sort instead.

08 Practice problems

Six problems, all solvable with this lesson alone

Do the first two on paper. The twist line tells you what each problem is really testing, so read it before you start writing code.

Count the work

Easy
Run the shifting version on 5 1 4 2 on paper and report three numbers: comparisons, slides, and key placements.
Follow-up
Comparisons and slides are different counts and most people report one number for both. The failing comparison that ends a scan still costs a comparison.
Show the hint
A comparison happens on every test of the while condition, including the one that fails — but no comparison happens when j falls off the left edge.

How long is the free head start

Easy
Given an array, return the largest k such that the first k values are already in non-decreasing order.
Follow-up
This is exactly the prefix insertion sort gets for free: rounds 1 through k−1 each cost one comparison and zero slides. It measures how much of the sort is already done.
Show the hint
Walk left to right and stop at the first index where A[i] < A[i-1].

One round, on its own

Medium
Given a sorted array of length n stored in a buffer of length n+1 and one new value, place the value so the buffer is sorted using only shifts, and return the index it landed at.
Follow-up
This is a single round of insertion sort lifted out of the loop, and you must copy starting from the right end or you overwrite the value you are about to read.
Show the hint
Start at index n−1 and copy each bigger value into the slot on its right before you look at the next one further left.

Count inversions for free

Medium
Return the number of inversions in an array — pairs i < j with A[i] > A[j] — by counting the slides that insertion sort performs.
Follow-up
It proves the adaptivity claim instead of asserting it, and hands you an O(n²) inversion counter with no new code. Check it against a brute-force double loop.
Show the hint
Every slide moves exactly one element past the key, and that element-and-key pair was exactly one inversion, so nothing gets counted twice.

One character kills stability

Medium
Sort a list of (name, score) pairs by score with insertion sort and return the order of names; then change the scan test from > to >= and return the order again.
Follow-up
The two answers can only differ where scores tie, so you have to build the tie deliberately. That single character is the entire definition of stability.
Show the hint
Use an input where two records share a score and start in a known order, such as (A,5) (B,3) (C,5).

Binary insertion sort

Hard
Rewrite insertion sort so the insertion point is found by binary search over the sorted prefix, and return both the total comparison count and the total slide count.
Follow-up
Comparisons drop to O(n log n) but total running time stays O(n²). Name which half of the work refused to get faster, and explain why that half is what sets the complexity.
Show the hint
Binary search tells you where the key goes, but something still has to move every value between that position and slot i one place right.