Insertion sort

Cost and properties

compares	~n²/4 average
best case	n−1 — already sorted
exchanges	= number of inversions
stable	yes

Reference: Sedgewick & Wayne, §2.1.

Insertion sort in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def insertion_sort(a):
    # INVARIANT: a[0..i-1] is sorted (but not necessarily final -- a later
    # key can still slide into the middle of it).
    for i in range(1, len(a)):
        j = i
        while j > 0 and a[j] < a[j - 1]:  # swap left while out of order
            a[j], a[j - 1] = a[j - 1], a[j]
            j -= 1
    return a

Why it works

The invariant, and how it differs from selection sort

a[0..i-1] is sorted — but not final. Selection sort places a key forever; insertion sort keeps a sorted prefix that later keys can still be inserted into. That is why it can exploit existing order and selection sort cannot.

Cost = inversions

Each exchange fixes exactly one inversion (a pair out of order), so the number of exchanges is precisely the number of inversions in the input, and compares are exchanges + at most n−1. Consequently insertion sort runs in linear time on partially sorted input — an array with a constant number of inversions per element sorts in O(n).

That is not a curiosity: it is why real sorting libraries switch to insertion sort for small or nearly-ordered subarrays, and why shellsort's h-sorted passes are cheap.

Stability

The loop stops on a[j] < a[j-1], strictly less. Equal keys never swap, so their original order survives — insertion sort is stable. Change that to <= and you break stability and waste time.

Watch for

The j > 0 test must come first: Python's and short-circuits, so a[j-1] is never evaluated with j == 0. Reverse the two conditions and the code reads a[-1], silently comparing against the last element of the array.

What to try in the animation

Compare already sorted (n−1 compares, zero exchanges) with reverse sorted (the full ~n²/2). No other elementary sort spreads that widely.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• random — 7 10 5 3 8 4 2 9 6 1
• SORTEXAMPLE (course) — S O R T E X A M P L E
• already sorted — 1 2 3 4 5 6 7 8 9 10
• reverse sorted — 10 9 8 7 6 5 4 3 2 1
• all equal — 5 5 5 5 5 5 5 5
• few distinct — 2 1 2 1 3 1 2 3 1 2

Open Insertion sort in the player →

The rest of Elementary sorts

• Selection sort Find the smallest remaining key and swap it into place.
• Shellsort Insertion sort, but comparing keys h apart.
• Knuth shuffle Swap each item with a random earlier one.