ZetCode

Python insertion sort

last modified November 18, 2026 Python 3.15

In this article we explain the insertion sort algorithm in Python. We implement and trace it, measure its work on different inputs, add key functions, and use the bisect module for binary insertion and for keeping a list sorted as new items arrive.

In everyday Python code we sort with list.sort or sorted. Their algorithm, Timsort, uses binary insertion sort internally to build short sorted runs, so insertion sort is not only a textbook example.

Insertion sort algorithm

Insertion sort works the way many people sort playing cards in their hand. The list is divided into a sorted prefix and an unsorted rest. The algorithm takes the first element of the unsorted rest and inserts it at the correct position in the sorted prefix, shifting greater elements one position to the right. It repeats this until the unsorted part is empty.

PropertyValue
Best case timeO(n), already sorted input
Average case timeO(n2)
Worst case timeO(n2), reversed input
Extra spaceO(1), sorts in place
Stableyes
Onlineyes, can sort data as it arrives

Insertion sort is adaptive: the closer the input is to sorted order, the less work it does. It is a good choice for small or nearly sorted lists.

Insertion sort example

The following is a basic implementation of insertion sort.

insertion_sort.py
def insertion_sort(vals):
    for i in range(1, len(vals)):
        key = vals[i]
        j = i - 1
        while j >= 0 and vals[j] > key:
            vals[j + 1] = vals[j]
            j -= 1
        vals[j + 1] = key


nums = [12, 11, 13, 5, 6, 7]
insertion_sort(nums)
print(nums)

The element at index i is saved in key. The while loop walks the sorted prefix from right to left and moves every greater element one position to the right. When it finds an element that is not greater, or reaches the start of the list, the key is placed into the gap. The function sorts the list in place.

$ python insertion_sort.py
[5, 6, 7, 11, 12, 13]

Tracing the algorithm

We print the sorted prefix and the unsorted rest after each insertion.

insertion_trace.py
def insertion_sort(vals):
    print(f'start   {vals[:1]} | {vals[1:]}')
    for i in range(1, len(vals)):
        key = vals[i]
        j = i - 1
        while j >= 0 and vals[j] > key:
            vals[j + 1] = vals[j]
            j -= 1
        vals[j + 1] = key
        print(f'put {key:>2}  {vals[:i + 1]} | {vals[i + 1:]}')


insertion_sort([7, 3, 9, 1, 5, 2])

The sorted prefix grows by one element in each step. Note that the prefix is sorted, but its elements are not necessarily in their final positions; the 1 and the 2 still have to be inserted before them.

$ python insertion_trace.py
start   [7] | [3, 9, 1, 5, 2]
put  3  [3, 7] | [9, 1, 5, 2]
put  9  [3, 7, 9] | [1, 5, 2]
put  1  [1, 3, 7, 9] | [5, 2]
put  5  [1, 3, 5, 7, 9] | [2]
put  2  [1, 2, 3, 5, 7, 9] | []

Shifts and inversions

An inversion is a pair of elements that are in the wrong order. Every shift of insertion sort removes exactly one inversion, so the number of shifts equals the number of inversions in the input.

shifts.py
import random


def insertion_sort(vals):
    comparisons = shifts = 0
    for i in range(1, len(vals)):
        key = vals[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if vals[j] <= key:
                break
            vals[j + 1] = vals[j]
            shifts += 1
            j -= 1
        vals[j + 1] = key
    return comparisons, shifts


def inversions(vals):
    return sum(1 for i in range(len(vals))
               for j in range(i + 1, len(vals)) if vals[i] > vals[j])


rng = random.Random(3)
n = 100
nearly = list(range(n))
for _ in range(5):
    i = rng.randrange(n - 1)
    nearly[i], nearly[i + 1] = nearly[i + 1], nearly[i]

inputs = {
    'sorted': list(range(n)),
    'nearly sorted': nearly,
    'random': rng.sample(range(n), n),
    'reversed': list(range(n, 0, -1)),
}

print(f'{"input":<14}{"inversions":>11}{"shifts":>8}{"comparisons":>13}')
for name, vals in inputs.items():
    inv = inversions(vals)
    comparisons, shifts = insertion_sort(vals.copy())
    print(f'{name:<14}{inv:>11}{shifts:>8}{comparisons:>13}')

We count comparisons and shifts on four inputs of 100 elements. The inversions function counts the out-of-order pairs directly. The sorted list needs no shifts and only n - 1 comparisons. The nearly sorted list has five swapped neighbours and costs just five extra comparisons. A random list has about n2/4 inversions and the reversed list has the maximum of n(n - 1)/2.

$ python shifts.py
input          inversions  shifts  comparisons
sorted                  0       0           99
nearly sorted           5       5          104
random               2778    2778         2873
reversed             4950    4950         4950

Key functions and descending order

We add the key and reverse parameters known from sorted.

insertion_key.py
def insertion_sort(vals, key=None, reverse=False):
    if key is None:
        key = lambda e: e
    for i in range(1, len(vals)):
        item = vals[i]
        k = key(item)
        j = i - 1
        while j >= 0 and (key(vals[j]) < k if reverse else key(vals[j]) > k):
            vals[j + 1] = vals[j]
            j -= 1
        vals[j + 1] = item


users = [
    ('John', 'Doe', 1230),
    ('Lucy', 'Novak', 670),
    ('Ben', 'Walter', 2050),
    ('Robin', 'Brown', 2300),
    ('Amy', 'Doe', 1250),
    ('Joe', 'Draker', 1190),
    ('Janet', 'Doe', 980),
]

insertion_sort(users, key=lambda u: u[2], reverse=True)
for user in users:
    print(user)

print()

insertion_sort(users, key=lambda u: u[1])
for user in users:
    print(user)

The key of the inserted item is computed once per insertion. With reverse=True, elements with a smaller key are shifted to the right. First we sort users by salary in descending order, then by last name. The three users named Doe stay in the salary order from the first sort, because insertion sort is stable and never moves an element past an equal one.

$ python insertion_key.py
('Robin', 'Brown', 2300)
('Ben', 'Walter', 2050)
('Amy', 'Doe', 1250)
('John', 'Doe', 1230)
('Joe', 'Draker', 1190)
('Janet', 'Doe', 980)
('Lucy', 'Novak', 670)

('Robin', 'Brown', 2300)
('Amy', 'Doe', 1250)
('John', 'Doe', 1230)
('Janet', 'Doe', 980)
('Joe', 'Draker', 1190)
('Lucy', 'Novak', 670)
('Ben', 'Walter', 2050)

Binary insertion sort

The sorted prefix allows binary search for the insertion point. This reduces the number of comparisons to O(n log n). The number of element moves stays O(n2), but moves are cheap compared to comparisons of complex objects.

binary_insertion.py
import bisect
import random


def insertion_sort(vals):
    comparisons = 0
    for i in range(1, len(vals)):
        key = vals[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if vals[j] <= key:
                break
            vals[j + 1] = vals[j]
            j -= 1
        vals[j + 1] = key
    return comparisons


class Counted:
    comparisons = 0

    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        Counted.comparisons += 1
        return self.val < other.val


def binary_insertion_sort(vals):
    for i in range(1, len(vals)):
        key = vals[i]
        pos = bisect.bisect_right(vals, key, 0, i)
        vals[pos + 1:i + 1] = vals[pos:i]
        vals[pos] = key


rng = random.Random(5)
data = rng.sample(range(1000), 1000)

linear = insertion_sort(data.copy())

items = [Counted(v) for v in data]
binary_insertion_sort(items)
assert [e.val for e in items] == sorted(data)

print(f'linear search comparisons: {linear}')
print(f'binary search comparisons: {Counted.comparisons}')

The bisect_right function finds the insertion point in the prefix vals[0:i]; using the right-most position keeps the sort stable. The slice assignment shifts the elements in one step. To count the comparisons made by bisect, we wrap the numbers in a class that counts calls of __lt__. For 1000 random numbers the binary version makes about 30 times fewer comparisons.

$ python binary_insertion.py
linear search comparisons: 254344
binary search comparisons: 8583

Sorting data as it arrives

Insertion sort is an online algorithm: it can sort a sequence whose elements arrive one at a time. The bisect.insort function inserts an item into a sorted list and keeps it sorted.

online_sort.py
import bisect

readings = [21.5, 19.0, 23.2, 20.1, 22.8, 18.4, 21.5]
window = []

for value in readings:
    bisect.insort(window, value)
    mid = len(window) // 2
    if len(window) % 2:
        median = window[mid]
    else:
        median = (window[mid - 1] + window[mid]) / 2
    print(f'{value:5}  {window}  median {median}')

We insert temperature readings one by one and compute the running median after each reading. Because the list is always sorted, the median is the middle element, or the average of the two middle elements.

$ python online_sort.py
 21.5  [21.5]  median 21.5
 19.0  [19.0, 21.5]  median 20.25
 23.2  [19.0, 21.5, 23.2]  median 21.5
 20.1  [19.0, 20.1, 21.5, 23.2]  median 20.8
 22.8  [19.0, 20.1, 21.5, 22.8, 23.2]  median 21.5
 18.4  [18.4, 19.0, 20.1, 21.5, 22.8, 23.2]  median 20.8
 21.5  [18.4, 19.0, 20.1, 21.5, 21.5, 22.8, 23.2]  median 21.5

The key parameter of bisect

Since Python 3.10, the bisect functions accept a key parameter.

insort_key.py
import bisect
from operator import itemgetter

tasks = []

for task in [('backup', 3), ('deploy', 1), ('report', 2), ('alert', 1)]:
    bisect.insort(tasks, task, key=itemgetter(1))

print(tasks)

pos = bisect.bisect_left(tasks, 2, key=itemgetter(1))
print('first task with priority 2:', tasks[pos])

The tasks are kept sorted by priority. The insort functions apply the key to the inserted item. The search functions such as bisect_left do not; they expect a key value, here the priority 2. The tasks with priority 1 stay in insertion order because insort is an alias of insort_right.

$ python insort_key.py
[('deploy', 1), ('alert', 1), ('report', 2), ('backup', 3)]
first task with priority 2: ('report', 2)

Benchmark

We compare insertion sort with sorted on random and on nearly sorted data.

benchmark.py
import random
import timeit


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


rng = random.Random(11)
n = 2000
random_data = [rng.randint(0, 10_000) for _ in range(n)]
nearly_sorted = sorted(random_data)
for _ in range(20):
    i, j = rng.randrange(n), rng.randrange(n)
    nearly_sorted[i], nearly_sorted[j] = nearly_sorted[j], nearly_sorted[i]

for name, data in [('random', random_data), ('nearly sorted', nearly_sorted)]:
    t_ins = timeit.timeit(lambda: insertion_sort(data.copy()), number=3) / 3
    t_sorted = timeit.timeit(lambda: sorted(data), number=3) / 3
    print(f'{name:<14} insertion sort {t_ins:8.5f} s  sorted {t_sorted:8.6f} s')

The nearly sorted list differs from the sorted one by 20 random swaps. Insertion sort is many times faster on it than on random data, which shows that it is adaptive. The built-in sorted also detects existing runs and is faster on nearly sorted data. The times vary between runs and machines.

$ python benchmark.py
random         insertion sort  0.04060 s  sorted 0.000166 s
nearly sorted  insertion sort  0.00181 s  sorted 0.000031 s

Source

Sorting Techniques – Python documentation

bisect – Python documentation

In this article we have implemented insertion sort in Python and used the bisect module for binary insertion. See also Python bubble sort, Python shell sort, Python selection sort, and Python merge sort.

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all Python tutorials.