Sorting Tested code in 3 languages

Insertion Sort, Visualized Step by Step

Take the next value, slide it left past every bigger value in the sorted part, drop it in the gap. Press play to watch every comparison and shift, next to the exact line of code that runs.

Crio.Do · Last updated 19 November 2026

Interactive insertion sort

Sort indices 0–7 (8 values). Index 0 on its own counts as a sorted part; insert the others into it one by one.

0Comparisons
0Shifts
1/–Step
def insertion_sort(a):    for i in range(1, len(a)):        key = a[i]        j = i - 1        while j >= 0 and a[j] > key:            a[j + 1] = a[j]            j -= 1        a[j + 1] = key

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How insertion sort works

Insertion sort builds the sorted result one value at a time. The left part of the array is always sorted. Take the next value, called the key, and walk left through the sorted part: every value bigger than the key moves one place right. When you reach a value that is not bigger, or the front of the array, the key drops into the gap.

It is how most people sort a hand of playing cards. You pick up one card at a time and slide it into place among the cards you are already holding. You never look at the cards still on the table until you pick them up.

This page uses the shifting version, not the swapping one. The key is held aside in a variable while bigger values are copied one place right, so each step of the walk costs one write instead of a three-write swap. In the animation the gap is the dashed outline: its old value has already been copied right, so it is free to overwrite.

The comparison is a strict a[j] > key, so the walk stops at a value equal to the key. Equal values therefore keep their original order: insertion sort is stable. Every shift fixes exactly one pair of values that were in the wrong order (an inversion), so the number of shifts equals the number of inversions in the input.

The algorithm in 5 steps

  1. 1 Treat index 0 on its own as a sorted part.
  2. 2 Take the next value as the key and set j to the index just left of it.
  3. 3 While j >= 0 and a[j] > key, copy a[j] one place right and move j left.
  4. 4 Write the key into the gap at j + 1. The sorted part is now one value longer.
  5. 5 Repeat until every value has been inserted.

Worked example

Here is the full run on a fixed array, generated by the same code as the visualizer. Each row shows the array right after one key has been inserted; the comparisons and shifts in between are counted in the total but not listed.

Input: [5, 2, 4, 6, 1, 3]

  1. Step 5 j ran off the front (every sorted value was bigger), so 2 goes to index 0. Indices 0–1 are now sorted: 2, 5. 254613
  2. Step 10 Put 4 into the free slot, index 1. Indices 0–2 are now sorted: 2, 4, 5. 245613
  3. Step 13 6 stays at index 3: it was already in place. Indices 0–3 are now sorted: 2, 4, 5, 6. 245613
  4. Step 23 j ran off the front (every sorted value was bigger), so 1 goes to index 0. Indices 0–4 are now sorted: 1, 2, 4, 5, 6. 124563
  5. Step 32 Put 3 into the free slot, index 2. Indices 0–5 are now sorted: 1, 2, 3, 4, 5, 6. 123456

Total for this run: 12 comparisons and 9 shifts, in 33 animation steps. Result: 1, 2, 3, 4, 5, 6.

Time and space complexity

Best

O(n)

Already sorted input: each key is compared once with its left neighbour and stays put, so n − 1 comparisons and no shifts.

Average

O(n²)

A random array has about n²/4 inversions, and each one costs a shift, so the work grows with the square of n.

Worst

O(n²)

Reverse-sorted input: every key walks to the front, n(n − 1)/2 comparisons and as many shifts.

Space

O(1)

Only the key and the index j are stored. No extra array, no recursion.

Stable:
Yes
In place:
Yes
Adaptive:
Yes
Online:
Yes

Six sorts, same 8 numbers

Comparison counts from running each algorithm on the visualizer's array, then on the same numbers already sorted and in reverse order. Computed from the code on these pages, not typed in.

AlgorithmComparisonsMovesSorted inputReversed input
Insertion sort 1713 shifts728
Selection sort 285 swaps2828
Bubble sort 2513 swaps728
Merge sort 1624 writes1212
Quick sort 385 swaps3132
Heap sort 2619 swaps2724

The last two columns are comparisons too. Exact counts depend on the input and the variant (this page's insertion sort shifts values instead of swapping them), which is why complexity is stated as growth, not exact numbers.

When to use it, and when not to

Good fit

  • Small arrays, up to a few dozen values. The loop is tiny, needs no recursion or extra memory, and beats O(n log n) sorts at that size, which is why library sorts switch to it for short ranges.
  • Nearly sorted data, such as a sorted list with a few new entries appended. The cost is n plus the number of inversions, so a handful of misplaced values costs almost nothing.
  • Data that arrives one value at a time (an online algorithm): each new value is inserted into an already sorted list as it comes in.
  • Inside hybrid sorts: Python's Timsort extends short runs with binary insertion sort, and quick sort implementations often hand small partitions to insertion sort.

Pick something else when

  • Large arrays in random order. At n = 100,000 a random array has about 2.5 billion inversions to fix; use the built-in sort, merge sort or quick sort.
  • Reverse-sorted or adversarial input, where every key walks the whole sorted part.

Common mistakes and bugs

  1. 1.Writing >= instead of > in the loop

    The output is still sorted, but the walk now moves past values equal to the key, so equal values swap order and the sort is no longer stable. It also does extra shifts on data with many duplicates.

  2. 2.Checking a[j] before j >= 0

    Write j >= 0 and a[j] > key, in that order. With the order reversed, the loop reads a[-1]: Java throws an exception, JavaScript reads undefined, and Python silently reads the last element.

  3. 3.Not saving the key first

    The first shift overwrites a[i]. Without key = a[i] before the loop, the value you are inserting is lost and a copy of its neighbour takes its place.

  4. 4.Writing the key to a[j] instead of a[j + 1]

    When the loop stops, j points at the first value that is not bigger than the key (or at -1). The key belongs one place to the right of it.

  5. 5.Starting the outer loop at 0

    Index 0 has nothing on its left, so starting at 0 just wastes a pass; starting at 1 is correct. Starting at 2 is the real bug: index 1 is never inserted, and a smaller value there stays out of place.

Interview questions

Try answering before you open the model answer.

Q1 Why does insertion sort run in close to O(n) on nearly sorted data?

Model answer: Each shift fixes exactly one inversion, and each key costs at most one comparison that does not lead to a shift. So the total work is O(n + d), where d is the number of inversions. If every value is at most k places from its final position, d is at most n·k and the sort is O(n·k).

Q2 Why do library sorts like Timsort fall back to insertion sort for small inputs?

Model answer: On a few dozen values the constant factors decide, not the growth rate. Insertion sort has no recursion, no extra buffer and a tight loop over neighbouring memory, and short runs in real data are often partly sorted already. Timsort uses binary insertion sort to extend short runs before merging them.

Q3 Does using binary search to find the insert position make insertion sort O(n log n)?

Model answer: No. Binary insertion sort cuts comparisons to O(n log n), but every value bigger than the key still has to move one place right, and that is O(n²) moves in the worst case for an array. It helps when comparisons are expensive, such as comparing long strings.

Q4 Sort a linked list using insertion sort.

Model answer: Keep a dummy head for the sorted list. Take nodes off the input one by one, walk the sorted list from the dummy to find the first node bigger than the current one, and relink the current node before it. No values move, only pointers: O(n²) time, O(1) extra space.

Q5 How many shifts does insertion sort make on a given array?

Model answer: Exactly the number of inversions: pairs i < j with a[i] > a[j]. Each shift swaps one adjacent out-of-order pair, which removes exactly one inversion. To count inversions without running an O(n²) sort, use merge sort and count during the merges in O(n log n).

Frequently asked questions

What is the time complexity of insertion sort?

O(n) in the best case, when the array is already sorted: n − 1 comparisons and no shifts. O(n²) on average and in the worst case, when the array is reversed and every value walks to the front. Extra space is O(1), and the cost on any input is about n plus the number of inversions.

Is insertion sort stable?

Yes. The inner loop only moves values that are strictly bigger than the key, so it stops at an equal value and the key lands to its right. Equal values keep their original order. Changing > to >= still sorts correctly but breaks stability, a common follow-up question in interviews.

Is insertion sort better than bubble sort?

Almost always. Both are O(n²), stable and in place, and both make one move per inversion. But insertion sort shifts with single writes instead of three-write swaps, and its walk stops as soon as the key is in place. On random input it does about half the comparisons of bubble sort.

When is insertion sort actually used in real code?

For small or nearly sorted inputs, mostly inside other sorts. Python's Timsort extends short runs with binary insertion sort before merging, and many quick sort and introsort implementations finish small ranges with insertion sort. On its own, it suits data that arrives one value at a time.

What is the difference between insertion sort and selection sort?

Insertion sort takes the next value and finds its place in the sorted part; selection sort finds the smallest remaining value and puts it next. Insertion sort adapts to the input, from O(n) on sorted data to O(n²), and is stable. Selection sort always does n(n − 1)/2 comparisons but at most n − 1 swaps.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3rd ed., MIT Press, 2009)
    Section 2.1, Insertion sort, with the loop-invariant proof; Problem 2-4 on inversions.
  2. Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., 1998)
    Section 5.2.1, Sorting by insertion.
  3. Tim Peters, listsort.txt, CPython source
    Timsort's design notes: short runs are extended with binary insertion sort.

The animation, the worked example and the step counts are all generated by one implementation of insertion sort, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms