Insertion Sort in Python (With Step-by-Step Output)

Python insertion sort builds a sorted list one item at a time: take the next value, shift every bigger value one place right, and drop the value into the gap. It’s how most people sort a hand of cards:

for i in range(1, len(a)):
    key, j = a[i], i - 1
    while j >= 0 and a[j] > key:
        a[j + 1] = a[j]; j -= 1
    a[j + 1] = key

I traced and timed every version here on Python 3.12.5, so the pass-by-pass output and comparison counts are real.

You’ll see the algorithm step by step, a version with key and reverse for sorting records, when it’s fast and when it’s slow, how it compares to sorted(), and the bisect shortcut.

How insertion sort works in Python

Think of everything left of position i as already sorted. Each pass takes a[i], slides larger values right, and inserts it where it belongs. Printing each pass makes that visible:

def insertion_sort(items, show=False):
    a = list(items)                          # sort a copy
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:         # shift bigger items one place right
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key                       # drop the key into the gap
        if show:
            print(f"pass {i}: insert {key:>2} -> {a}")
    return a

print(insertion_sort([29, 10, 14, 37, 13], show=True))

Output:

pass 1: insert 10 -> [10, 29, 14, 37, 13]
pass 2: insert 14 -> [10, 14, 29, 37, 13]
pass 3: insert 37 -> [10, 14, 29, 37, 13]
pass 4: insert 13 -> [10, 13, 14, 29, 37]
[10, 13, 14, 29, 37]

The function sorts a copy, so the original list is left alone. Drop the list(items) line if you want an in-place sort like list.sort().

Insertion sort with key and reverse (sorting records)

Your real data is usually records, not bare numbers. Adding key and reverse arguments, like the built-ins have, lets you sort orders by total:

def insertion_sort(items, key=lambda x: x, reverse=False):
    a = list(items)
    for i in range(1, len(a)):
        item, k = a[i], key(a[i])
        j = i - 1
        while j >= 0 and ((key(a[j]) < k) if reverse else (key(a[j]) > k)):
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = item
    return a

orders = [("Austin", 89.50), ("Denver", 42.00), ("Boston", 89.50), ("Tampa", 15.25), ("Reno", 42.00)]

for city, total in insertion_sort(orders, key=lambda o: o[1]):
    print(f"{city:<7} ${total:>6.2f}")          # ties keep their original order (stable)
print([c for c, _ in insertion_sort(orders, key=lambda o: o[1], reverse=True)])

Output:

Tampa   $ 15.25
Denver  $ 42.00
Reno    $ 42.00
Austin  $ 89.50
Boston  $ 89.50
['Austin', 'Boston', 'Denver', 'Reno', 'Tampa']

Insertion sort is stable because it only moves an item past values that are strictly greater. Python’s own sorted() is stable too. See sorting a list of tuples for the built-in way.

When is insertion sort fast or slow?

On already sorted data it does one comparison per item, which is linear time. On reversed data it compares every pair, which is quadratic. Counting comparisons for 1,000 items shows the gap:

import random

def count_comparisons(items):
    a, comps = list(items), 0
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0:
            comps += 1
            if a[j] <= key:
                break
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return comps

n = 1_000
random.seed(1)
nearly = list(range(n))
for i in random.sample(range(n - 1), 20):          # swap 20 neighboring pairs
    nearly[i], nearly[i + 1] = nearly[i + 1], nearly[i]
cases = {"already sorted": list(range(n)),
         "nearly sorted": nearly,
         "random": random.sample(range(n), n),
         "reversed": list(range(n, 0, -1))}
for name, data in cases.items():
    print(f"{name:<15} {count_comparisons(data):>8,} comparisons")

Output:

already sorted       999 comparisons
nearly sorted      1,019 comparisons
random           253,231 comparisons
reversed         499,500 comparisons

Case	Time complexity	When it happens
Best	O(n)	Already or nearly sorted
Average	O(n²)	Random order
Worst	O(n²)	Reverse order
Extra memory	O(1)	Sorts in place

Insertion sort vs Python’s sorted()

For your real programs, use sorted() or list.sort(). They run Timsort in C, which actually uses insertion sort on short runs internally. On 3,000 random numbers the difference is huge:

import random
import timeit

def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

data = random.sample(range(1_000_000), 3_000)
assert insertion_sort(data) == sorted(data)
t_ins = timeit.timeit(lambda: insertion_sort(data), number=3) / 3
t_built = timeit.timeit(lambda: sorted(data), number=3) / 3
print(f"insertion sort: {t_ins:.3f} s | sorted(): {t_built * 1000:.3f} ms")

Output:

insertion sort: 0.138 s | sorted(): 0.253 ms

Insertion sort is still worth knowing for interviews, for tiny lists, and for understanding how other algorithms work. Compare it with selection sort and the rest in sorting algorithms in Python.

Keeping a list sorted with bisect.insort

If you add items one at a time and want the list always sorted, bisect.insort() does insertion sort’s “find the spot and insert” step with a binary search:

import bisect

leaderboard = [120, 340, 560, 780]          # kept sorted at all times
for new_score in [450, 90, 900, 560]:
    bisect.insort(leaderboard, new_score)    # binary search for the spot, then insert
    print(f"added {new_score:>3}: {leaderboard}")

print("rank of 600:", len(leaderboard) - bisect.bisect_right(leaderboard, 600) + 1)

Output:

added 450: [120, 340, 450, 560, 780]
added  90: [90, 120, 340, 450, 560, 780]
added 900: [90, 120, 340, 450, 560, 780, 900]
added 560: [90, 120, 340, 450, 560, 560, 780, 900]
rank of 600: 3

Finding the spot is a binary search, the same idea as in binary search in Python; the insert itself still shifts items, so it suits lists of moderate size.

More algorithm walkthroughs to try:

• Breadth first search in Python
• Depth first search in Python
• Greatest common divisor in Python
• Python while loop

Frequently asked questions