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.
| Property | Value |
|---|---|
| Best case time | O(n), already sorted input |
| Average case time | O(n2) |
| Worst case time | O(n2), reversed input |
| Extra space | O(1), sorts in place |
| Stable | yes |
| Online | yes, 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.
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.
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.
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.
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.
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.
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.
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.
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
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
List all Python tutorials.