Insertion Sort Visualizer — Step-by-Step Animation

What is Insertion Sort?

Insertion sort builds the sorted array one element at a time, the way most people sort a hand of cards: take the next element (the key), shift every larger element of the sorted prefix one place right, and drop the key into the gap. It is O(n²) on average and in the worst case but O(n) on nearly sorted input, and it is stable, in-place and online — which is why real sorting libraries use it for small arrays.

How it works

Treat A[0] as a sorted prefix of length one.
Lift out the next element, key = A[i], leaving a gap at index i.
Walk left with j = i − 1: while A[j] > key, shift A[j] one slot right into the gap.
When A[j] ≤ key (or j runs off the front), drop key into the gap at j + 1. The prefix A[0..i] is sorted again.
Repeat for i = 1 … n − 1.

Worked example: sorting [38, 27, 43, 3, 9, 82, 10]

The visualizer above opens on this array:

key 27: 38 shifts right and 27 goes to the front: [27, 38, 43, 3, 9, 82, 10].
key 43: already larger than 38 — one comparison, no shifts.
key 3: 43, 38 and 27 all shift: [3, 27, 38, 43, 9, 82, 10].
key 9: 43, 38 and 27 shift, then 3 ≤ 9 stops the scan: [3, 9, 27, 38, 43, 82, 10].
key 82: larger than 43, stays where it is.
key 10: 82, 43, 38 and 27 shift: [3, 9, 10, 27, 38, 43, 82].

Total: 15 comparisons and 11 shifts. Eleven is the number of inversions in the input — insertion sort makes exactly one shift per inversion.

Why insertion sort is fast on nearly sorted data

The work is easy to count: every shift removes exactly one inversion, and every key needs at most one extra comparison to stop. So insertion sort runs in O(n + I) time, where I is the number of inversions. Sorted input has I = 0 and costs n − 1 comparisons. Reversed input has I = n(n − 1)/2, the quadratic worst case. Random input has I ≈ n²/4, so the average is still quadratic.

That makes insertion sort adaptive: the closer the input is to sorted, the faster it runs. In the visualizer's Compare mode it wins the nearly-sorted race outright, far ahead of merge sort and quick sort.

Why libraries use it inside faster sorts

On small arrays constant factors beat Big-O. Insertion sort has no recursion, no extra memory and a tiny inner loop, so for a few dozen elements it outruns merge sort and quick sort. That is why:

Timsort (Python, Java objects, V8's Array.prototype.sort) uses binary insertion sort to grow short runs to a minimum length of 32–64 elements before merging them.
Introsort (C++ std::sort in libstdc++) stops the quick-sort recursion at partitions of 16 elements and finishes with insertion sort.
Shell sort is insertion sort run over shrinking gaps, so far-apart elements move early.

Insertion sort is also online: it can keep a list sorted while items arrive one at a time.

Insertion sort vs bubble and selection sort

vs bubble sort: both make one move per inversion, but insertion sort shifts (one write) instead of swapping, and its scan stops at the first smaller element — about half as many comparisons on random input.
vs selection sort: selection sort makes fewer writes (at most n − 1 swaps) but always n(n − 1)/2 comparisons; insertion sort compares less and adapts to presorted input.
Binary insertion sort finds each key's slot with binary search (O(log n) comparisons), but still shifts the elements, so it remains O(n²) moves.

Common mistakes and interview tips

Writing A[j] >= key in the loop condition: equal elements shift past each other and the sort is no longer stable.
Testing A[j] > key before j >= 0. In Python, A[-1] silently reads the last element when the key belongs at the front.
Swapping the key down step by step instead of shifting and writing it once — correct, but up to three times the writes.
Interview angle: “sort an array where every element is at most k places from its final position.” Insertion sort does it in O(nk); a min-heap of size k + 1 in O(n log k).

Time and space complexity

Case	Time	Space	Why
Best	O(n)	O(1)	Sorted input: each key needs one comparison and no shifts.
Average	O(n²)	O(1)	About n²/4 shifts — one per inversion.
Worst	O(n²)	O(1)	Reversed input: every key shifts past the whole prefix, n(n − 1)/2 shifts.

Insertion Sort in Python

def insertion_sort(A):
    # Sorts list A in place, ascending. Stable, O(1) extra space.
    n = len(A)
    for i in range(1, n):               # A[0..i-1] is already sorted
        key = A[i]                      # lift the next element out
        j = i - 1
        while j >= 0 and A[j] > key:    # strict > keeps it stable
            A[j + 1] = A[j]             # shift the bigger element right
            j -= 1
        A[j + 1] = key                  # drop key into the gap

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Is insertion sort stable?

Yes. A key stops at the first element that is less than or equal to it, so equal elements keep their original order.

What is the best case of insertion sort?

An already sorted array: n − 1 comparisons, no shifts, O(n) time. Nearly sorted input is almost as fast, because the cost is O(n + number of inversions).

Is insertion sort better than bubble sort?

Yes, in practice. Both are O(n²) and stable, but insertion sort makes about half the comparisons on random input and shifts elements instead of swapping them.

Why does Timsort use insertion sort?

On short runs insertion sort is faster than merging because it has almost no overhead, and real data often contains partly sorted stretches. Timsort uses binary insertion sort to build sorted runs, then merges the runs.

Is insertion sort an online algorithm?

Yes. It only needs the elements seen so far, so it can keep a growing list sorted as new items arrive, inserting each one into place.

Keep learning

Last updated 19 October 2026