cf.completefrontend
SORTING · FOUNDATION

Insertion sort

Sort a list by taking items one at a time and sliding each one left into its place among the items already sorted.

Time O(n²)Space O(1)5 practice problemsStep-through picture

The idea

Insertion sort grows a sorted part at the front of the list. At first, only the first item is in it. Then it takes the next item, called current, and slides it left past every bigger item, until it sits in the right place. Then it takes the next item, and so on.

Sliding means shifting: each bigger item moves one spot to the right to make room, and current drops into the gap. No item is ever swapped far away, so equal items keep their order. That makes insertion sort stable.

It is O(n²) in the worst case, but it is very fast on short lists and on lists that are already nearly sorted, because each item only slides a few spots. That is why real sorting code, including the TimSort behind Array.prototype.sort in V8, uses insertion sort for small pieces.

An everyday example

Sorting playing cards in your hand

You pick up cards one at a time. The cards in your hand are always in order. When you pick up a new card, you slide it in from the right, past every card bigger than it, and stop as soon as the card to its left is smaller or equal. Then you pick up the next card.

How the example maps to the code
In the exampleIn the code
The sorted cards in your handitems[0..i-1]
The new card you just picked upcurrent = items[i]
Moving a bigger card over to make roomitems[j + 1] = items[j]
Dropping the card into the gapitems[j + 1] = current

From the slow way to insertion sort

  1. Imagine the list arrives one item at a time, and you want to keep what you have so far sorted. The first item alone is sorted. When the second arrives, put it before or after the first. When the third arrives, find where it fits among the two, and so on. That is how most people sort playing cards as they are dealt.
  2. Where does the new item go? The items before it are already sorted, so walk left from the end of the sorted part. Every item bigger than the new one has to end up after it. As soon as you meet an item that is not bigger, you have found the spot: right after it.
  3. Swapping the new item left one step at a time would work, but each swap writes two values. A cheaper way is to save the new item in current, then shift each bigger item one step to the right into the gap, and write current once at the end. One write per step instead of two.
  4. In an array, the sorted part is just the front: items[0..i-1]. For each i from 1 to the end, save current = items[i], shift bigger items right with an index j that walks left, and drop current at j + 1. That loop is insertion sort.

How it works

  1. Treat items[0] as a sorted part of length one.
  2. For each i from 1 to the end, save current = items[i].
  3. Set j = i - 1. While j >= 0 and items[j] > current, shift items[j] one spot right and move j left.
  4. When the loop stops, items[j] is smaller or equal (or j is -1), so put current at j + 1.
  5. Now items[0..i] is sorted. Continue with the next i.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function insertionSort(items) {
  2. for (let i = 1; i < items.length; i++) {
  3. const current = items[i];
  4. let j = i - 1;
  5. while (j >= 0 && items[j] > current) {
  6. items[j + 1] = items[j];
  7. j--;
  8. }
  9. items[j + 1] = current;
  10. }
  11. return items;
  12. }

How fast it is

TimeO(n²)
Extra memoryO(1)

Each item slides past the bigger items before it. In a reversed list that is every earlier item, about n² / 2 shifts in total; in a sorted list it is none.

  • Best caseO(n)

    An already sorted list, like [1, 4, 6, 9]. Each current is checked against one item, which is not bigger, so there are no shifts.

  • Average caseO(n²)

    A random list has about n² / 4 inversions, and each costs one shift.

  • Worst caseO(n²)

    A reversed list like [9, 6, 4, 1]. Each item shifts past every earlier item: n × (n - 1) / 2 shifts.

Common mistakes

  • Swapping items[j] and items[j + 1] at every step instead of shifting. It works but does three writes per step instead of one.
  • Forgetting to save items[i] before the loop. The first shift overwrites it and the value is lost.
  • Writing the loop as items[j] >= current. Equal items then jump past each other and the sort is no longer stable.
  • Using it on large random lists. At 100,000 items it does billions of shifts; use the built-in sort or merge sort.

When to use it

Look for these clues in a problem:

  • The list is short (a few dozen items) or nearly sorted already.
  • Items arrive one at a time and the list must stay sorted after each one.
  • Equal items must keep their original order (a stable sort is needed).
  • The question asks how many shifts or moves it takes to sort.

Check yourself

Answer each one in your head first, then open it.

How many shifts does insertion sort make on [4, 3, 2, 1]?

Six, one per inversion: n × (n - 1) / 2 with n = 4. Each item shifts past every item before it.

Why must current be saved before the while loop?

The first shift writes items[j] into items[j + 1], which is items[i]. Without the saved copy, the value being inserted is lost.

What changes if the loop condition is items[j] >= current?

The list still sorts, but current moves past equal items, so equal items swap their order and the sort is no longer stable. It also does extra shifts.

Why is insertion sort fast on a list where every item is at most 3 places from its spot?

Each item can be out of order with at most 3 items before it, so it shifts at most 3 times. The total is at most 3n shifts, which is O(n).

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of every outer step is: items[0..i-1] is the first i items of the original list, in sorted order. With i = 1 that part is one item, and one item is always sorted.

One step keeps the rule. The while loop shifts every item in the sorted part that is bigger than current one place right, and it shifts them in order, so they stay sorted among themselves. It stops at the first item that is not bigger, or at the front. Writing current just after that item puts it after everything not bigger and before everything bigger, so items[0..i] is sorted.

Both loops end: i grows by one up to items.length, and j drops by one each shift and stops at -1 at the latest. When the outer loop ends, i equals items.length, so the rule says the whole list is sorted.

Each shift moves current past exactly one bigger item that was before it, which is one inversion fixed. That is why the total work is n plus the number of inversions, and why stopping at equal items (using >, not >=) keeps the sort stable.

Going deeper

3 more ideas

Why the front stays sorted

Before step i, the part items[0..i-1] is sorted. The step shifts every item bigger than current one place right, keeping their order, and puts current just after the last item that is not bigger. So items[0..i] is sorted afterwards. Because the shift stops at an equal item, equal items never pass each other, which is why the sort is stable.

How long it takes

Each shift fixes one out-of-order pair (an inversion), so the work is O(n + inversions). A sorted list has no inversions and takes O(n). A reversed list has about n² / 2 and takes O(n²). A list where every item is at most k places from its spot has at most n × k inversions, so it takes O(n × k).

Binary insertion sort

You can find where current goes with a binary search over items[0..i-1] instead of comparing one by one. That cuts comparisons to O(n log n), but the shifting is still O(n²) in the worst case. TimSort uses this version for short runs, because comparisons can be expensive when they call a user's comparator function.

Work it by hand

Every step in a table, with why

Sort 6 numbers with two 5s. Inserting 2 shows a long shift; inserting the second 5 shows the stop at an equal item.

items = [7, 3, 5, 8, 2, 5]

Stepicurrentjitems[j] > current?itemsWhat happensWhy
1130, then -17 > 3: yes[3, 7, 5, 8, 2, 5]Shift 7, place 3 at 07 moves to index 1. j falls to -1, so current goes to index 0.
2251, then 07 > 5, then 3 > 5: no[3, 5, 7, 8, 2, 5]Shift 7, place 5 at 1One shift. The loop stops at 3, which is not bigger.
33827 > 8: no[3, 5, 7, 8, 2, 5]No shift8 is already bigger than everything before it, so it is written back where it was.
44238 > 2: yes[3, 5, 7, 8, 8, 5]Shift 8 rightcurrent = 2 is saved, so overwriting index 4 loses nothing.
54227 > 2: yes[3, 5, 7, 7, 8, 5]Shift 7 rightThe gap moves one step left each time.
64215 > 2: yes[3, 5, 5, 7, 8, 5]Shift 5 rightThere are briefly two copies of a value; the gap is the left copy.
74203 > 2: yes[3, 3, 5, 7, 8, 5]Shift 3 rightj becomes -1, so j >= 0 fails and the loop ends.
842-1loop ends[2, 3, 5, 7, 8, 5]Place 2 at 0items[j + 1] = current writes 2 into index 0. Four shifts for one item.
95548 > 5: yes[2, 3, 5, 7, 8, 8]Shift 8 rightInsert the second 5.
105537 > 5: yes[2, 3, 5, 7, 7, 8]Shift 7 rightOne more shift.
115525 > 5: no[2, 3, 5, 5, 7, 8]Place 5 at 3The loop stops at the equal 5, so the second 5 lands after the first: the sort is stable.

It returns [2, 3, 5, 5, 7, 8] after 8 shifts. The list had exactly 8 out-of-order pairs, and each shift fixed one of them. The outer loop ends when i reaches items.length.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Insertion sortO(n²)O(1)The list is small (up to a few dozen items) or nearly sorted, or items arrive one at a time. It is stable and very fast in those cases.
Merge sortO(n log n)O(n)The list is large and in random order, and you need stability.
Shell sortO(n²)O(1)You want much better practical speed than insertion sort with no extra memory, and stability doesn't matter.
Bubble sortO(n²)O(1)Rarely. It does the same number of moves as insertion sort but with more writes and more comparisons.

Extra memory: O(1): just i, j, and current. The sort happens inside the array.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Insertion sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Insertion sort, Shell sort, Bubble sort O(n²)
  • Merge sort O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Insertion sort1001 million1 trillion
Merge sort339,96620 million
Shell sort1001 million1 trillion
Bubble sort1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty list or one item
i starts at 1, so i < items.length is false and nothing runs. The list is returned as it is.
Already sorted: [2, 4, 6, 8]
Each while check fails at once, so it makes 3 comparisons and 0 shifts: the O(n) best case.
Equal items: [5a, 3, 5b]
When 5b is inserted, the loop stops at 5a because 5a > 5b is false. Result [3, 5a, 5b]: equal items keep their order.
Each item is at most k places from its final spot, like a list sorted by time where a few events arrived late
Each item shifts at most k times, so the cost is O(n × k). For small k this is nearly linear and beats O(n log n) sorts.
A new item appended to a sorted list
Run just one step with i at the last index. It costs at most n shifts and keeps the list sorted, which is cheaper than sorting the whole list again.

Variations and follow-ups

Twists interviewers add

Binary insertion sort

Find the spot for current with a binary search over items[0..i-1], then shift. Comparisons drop to O(n log n), but shifts stay O(n²) in the worst case. It helps when comparisons are expensive, which is why TimSort uses it for short runs.

Shell sort

Run insertion sort on items gap places apart, with a shrinking gap, and finish with gap = 1. Far-away items move in big jumps first, so the final plain insertion sort has little left to do.

Insertion sort as a base case

Merge sort and quick sort spend a lot of time on tiny pieces. Many libraries switch to insertion sort when a piece has fewer than about 10 to 64 items, because its simple loop is faster there than more recursion.

Online sorting

Insertion sort works even if items arrive one at a time and you must keep the list sorted after each one. Each arrival is one outer step. For many arrivals into a large list, a balanced tree or heap is faster.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the data is "almost sorted", "each item is at most k positions away", or arrives as a stream that must stay sorted. Insertion sort's O(n + inversions) cost is the reason.
  • Explain it with the rule "the front part is sorted" and the picture of a gap moving left as bigger items shift right. Then point out the saved current: without it, the first shift overwrites the item.
  • Test by hand with a reversed list (every item travels to the front), a sorted list (no shifts), and a list with equal items, to show the stop at > keeps the sort stable.
  • The usual follow-up is "why does V8's sort still use insertion sort?". Because TimSort sorts short runs with binary insertion sort, where its low overhead beats any O(n log n) method.

Where frontend code uses it

The same idea in real UI code
  • V8's Array.prototype.sort is TimSort, which sorts short runs with binary insertion sort before merging them.
  • Keeping a small list sorted as items arrive, such as chat messages that come in mostly in order, is one insertion step per new item.
  • Re-sorting a table after a user edits one cell: the list was sorted before, so insertion sort only slides the one changed row.

Related algorithms