Why this matters
Real data is often almost in order already. A list of exam scores that was sorted yesterday has a few new scores added at the end. A playlist sorted by track number has one song moved to the front. A log file sorted by time has a few late entries near the bottom. Sorting such data from scratch throws away the order that is already there.
Insertion sort is a simple method that keeps that order. Its work depends on how far each value is from its final place, not on the total length of the list alone. When each value is already close to where it belongs, insertion sort finishes in close to one pass over the data. This lesson explains why, shows the step counts for several kinds of input, and shows how to measure the steps in Python.
Earlier lessons in this module covered bubble, selection and insertion sort on general input. This lesson looks only at the case where the input is nearly sorted, and counts the work exactly.
Terms used in this lesson
A sorted prefix is the first part of a list that is already in order. Insertion sort grows this part one value at a time, starting with a prefix of one value.
A comparison is one check that asks whether one value is bigger than another. Each comparison costs a little time.
A shift is one move that copies a value one position to the right to make room for a value that is being inserted. Shifts are the main cost of insertion sort.
An inversion is a pair of values where the bigger one comes first. In [3, 1, 2] there are two inversions: 3 before 1, and 3 before 2. The number of inversions is a plain measure of how far a list is from sorted order.
Nearly sorted means that most values are already in the right order, and the values that are out of place are only a short distance from their correct position. The exact meaning is given later in this lesson with numbers.
Step count means the number of basic actions a program performs. Here the steps are comparisons and shifts.
The idea, step by step
Insertion sort works like sorting a hand of playing cards. You pick up one card at a time from the table. You slide it left past every card in your hand that is bigger, and drop it where the next card on the left is smaller or equal. The cards in your hand are always in order, and you never go back to change them.
Here is the same method written for a list of numbers. The name a is the list, and the list indexes start at 0, so the first value is a[0].
def insertion_sort(a):
for i in range(1, len(a)):
value = a[i]
j = i - 1
while j >= 0 and a[j] > value:
a[j + 1] = a[j]
j -= 1
a[j + 1] = valueThe outer loop picks the value at position i, which is the next card. The inner loop moves to the left and shifts every bigger value one place to the right. When it finds a value that is not bigger, or when it runs out of list to the left, it stops. The picked value goes into the gap at j + 1.
Before the loop starts, the prefix a[0] is trivially sorted, because one value is always in order. Each time the outer loop runs, the prefix from position 0 up to i is sorted again.
A card-hand picture
Suppose the list is [5, 2, 4, 6, 1, 3]. Think of the first card, 5, as the hand. Now pick up 2. It is smaller than 5, so 5 slides right and 2 goes in front. The hand is now 2, 5. Pick up 4. It is smaller than 5 but bigger than 2, so 5 slides right and 4 goes between 2 and 5. The hand is now 2, 4, 5.
The same thing happens for every card. Each new card costs a few slides to the left, and the number of slides depends only on how many cards in the hand are bigger than it.
A trace with real output
The program below runs insertion sort on that list and prints the list after each insertion, together with running counts of comparisons and shifts. The counts are kept inside the function, so the trace can show them. The data is built in, so you can run it without typing input.
The output is:
start [5, 2, 4, 6, 1, 3]
insert 2: [2, 5, 4, 6, 1, 3] (comparisons so far 1, shifts so far 1)
insert 4: [2, 4, 5, 6, 1, 3] (comparisons so far 3, shifts so far 2)
insert 6: [2, 4, 5, 6, 1, 3] (comparisons so far 4, shifts so far 2)
insert 1: [1, 2, 4, 5, 6, 3] (comparisons so far 8, shifts so far 6)
insert 3: [1, 2, 3, 4, 5, 6] (comparisons so far 12, shifts so far 9)
done [1, 2, 3, 4, 5, 6] comparisons=12 shifts=9The trace uses a break inside the loop, so each comparison is counted before the test. It does the same work as the short form at the top of this lesson.
Read the line for insert 6. The value 6 is already bigger than 5, so the first comparison stops the loop. It costs one comparison and zero shifts. This is the best case for one insertion: the value is already in place.
Read the line for insert 1. The value 1 is smaller than all four values in the sorted part, so it must move all the way to the front. That costs four shifts and, because the loop ends at the start of the list, no final comparison.
The final line has 9 shifts. That number is not a coincidence, and the next section explains it.
Why the shift count equals the inversion count
Each shift moves one value past one value that is bigger than it and that comes before it in the list. In other words, each shift removes exactly one inversion. Insertion sort does not make any other kind of move, so the total number of shifts is exactly the number of inversions in the input.
Check this on the example. The list [5, 2, 4, 6, 1, 3] has these inversions:
- 5 comes before 2, 4, 1 and 3, which gives 4 inversions.
- 2 comes before 1, which gives 1 inversion.
- 4 comes before 1 and 3, which gives 2 inversions.
- 6 comes before 1 and 3, which gives 2 inversions.
The total is 4 + 1 + 2 + 2 = 9. The program also reported 9 shifts. Every shift in the program removed one of those 9 inversions.
This gives the key fact for this lesson. The work of insertion sort is the number of inversions in the input, plus a small amount for the checks. When data is nearly sorted, it has few inversions, so the work is small.
Counting the comparisons
Each outer loop run makes at least one comparison, because j starts at a valid index when i is 1 or more. The loop makes one more comparison when it stops for a reason other than running off the front of the list. So the number of comparisons is at most the number of shifts plus n - 1.
The exact relationship is comparisons = shifts + (n - 1) - f, where f is the number of values that moved all the way to the front of the list. In the example, n - 1 is 5, the shifts are 9, and two values (1 and 2) moved to the front. That gives 9 + 5 - 2 = 12 comparisons, which matches the output.
You do not need the exact formula to use the idea. The useful rule is: comparisons are about the number of shifts plus the list length. For a large list, the list length is a fixed cost that every sort pays. The shifts are the part that changes with the input.
Worked example 1: sorted, reversed and one value out of place
The first example uses three small lists of 10 values. The report function in the next section prints these rows for lists of 10 values. Each row shows how many comparisons and shifts the sort used.
sorted 1..10 n=10 comparisons=9 shifts=0 correct=True
one value out of place n=10 comparisons=10 shifts=1 correct=True
reversed 10..1 n=10 comparisons=45 shifts=45 correct=TrueThe sorted list needs only 9 comparisons. Each of the 9 values is checked once against the value before it, the check finds that value is not bigger, and the loop stops. There are no shifts at all.
The list with one value out of place, [1, 2, 4, 3, 5, 6, 7, 8, 9, 10], needs one shift. The value 3 is smaller than 4, so 4 moves one place right, and 3 drops into the gap. Comparisons are 10, which is 1 shift plus 9 comparisons, with no value moving to the front.
The reversed list needs 45 shifts. Every value must move past every value that came before it, so the number of shifts equals the number of pairs of positions, which is 10 times 9 divided by 2. This is the worst case for insertion sort. Its work grows with the square of the list length.
Put the three cases side by side. The sorted case does about n steps. The one-error case does n steps plus one shift. The reversed case does about n squared divided by 2 steps. The same code does very different amounts of work, because the amount of work depends on the order of the input.
Counting steps on larger inputs
The next program builds lists of three kinds: sorted, nearly sorted, and reversed. It counts comparisons and shifts for each size, and checks that the output matches Python's built-in sorted(). The nearly sorted lists are made by starting with 0, 1, 2, ... and doing random swaps. Each swap joins two positions that are at most k apart. The seed value is fixed, so the same numbers come out on every run.
import random
comparisons = 0
shifts = 0
def insertion_sort(a):
global comparisons, shifts
for i in range(1, len(a)):
value = a[i]
j = i - 1
while j >= 0:
comparisons += 1
if a[j] <= value:
break
a[j + 1] = a[j]
shifts += 1
j -= 1
a[j + 1] = value
def nearly_sorted(n, swaps, max_distance, seed):
a = list(range(n))
rng = random.Random(seed)
for _ in range(swaps):
i = rng.randrange(n)
j = min(n - 1, i + 1 + rng.randrange(max_distance))
a[i], a[j] = a[j], a[i]
return a
def report(label, data):
global comparisons, shifts
copy = list(data)
comparisons = 0
shifts = 0
insertion_sort(copy)
ok = copy == sorted(data)
print(f"{label:<28} n={len(data):<6} comparisons={comparisons:<10} shifts={shifts:<10} correct={ok}")
for n in [1000, 2000, 4000, 8000]:
report("sorted", list(range(n)))
report("nearly sorted (k=5)", nearly_sorted(n, n // 10, 5, 42))
report("reversed", list(range(n, 0, -1)))
print()The output from the run is below. The n column is the list length, and correct checks the result against sorted().
sorted n=1000 comparisons=999 shifts=0 correct=True
nearly sorted (k=5) n=1000 comparisons=1369 shifts=370 correct=True
reversed n=1000 comparisons=499500 shifts=499500 correct=True
sorted n=2000 comparisons=1999 shifts=0 correct=True
nearly sorted (k=5) n=2000 comparisons=2841 shifts=842 correct=True
reversed n=2000 comparisons=1999000 shifts=1999000 correct=True
sorted n=4000 comparisons=3999 shifts=0 correct=True
nearly sorted (k=5) n=4000 comparisons=5787 shifts=1788 correct=True
reversed n=4000 comparisons=7998000 shifts=7998000 correct=True
sorted n=8000 comparisons=7999 shifts=0 correct=True
nearly sorted (k=5) n=8000 comparisons=11577 shifts=3578 correct=True
reversed n=8000 comparisons=31996000 shifts=31996000 correct=TrueThe nearly sorted rows use Python's random number generator with seed 42. A Java run with a different random generator gives different counts for the same idea. The shape of the numbers is what matters.
Look at the sorted rows. The count grows in a straight line: 999, 1999, 3999, 7999. Doubling the list length roughly doubles the work.
Look at the reversed rows. Doubling the list length roughly quadruples the work: 499500 becomes 1999000, then 7998000, then 31996000. This is the growth of the square of n. Insertion sort on reversed input is slow for large lists.
The nearly sorted rows sit between the two. Doubling the list length still roughly doubles the work, which is what a near-linear method should do. At n = 8000, the nearly sorted case takes about 11,577 comparisons, while the reversed case takes about 32 million. The nearly sorted input is about 2,800 times cheaper for the same length.
Worked example 2: how the cost depends on the distance k
The number k in the program is the largest distance a value can be from its final place, in terms of the swaps that made the input. A smaller k means that each value is closer to where it belongs, so there are fewer inversions. A variant of the same program keeps the list length at 8000 and changes k. It passes nearly_sorted(8000, 800, k, 7) to report for each k. It uses 800 swaps every time, which is one tenth of the length, and the seed is 7 for all four rows.
nearly sorted k=1 n=8000 comparisons=8719 shifts=720 correct=True
nearly sorted k=5 n=8000 comparisons=11493 shifts=3494 correct=True
nearly sorted k=20 n=8000 comparisons=21907 shifts=13908 correct=True
nearly sorted k=100 n=8000 comparisons=75585 shifts=67586 correct=TrueWith k = 1, each swap joins two neighbouring positions. The list has only about 720 inversions, and the sort takes about 8,719 comparisons. That is about n plus the small number of inversions.
With k = 100, the swaps can reach 100 positions away. The number of shifts rises to about 67,000, and the comparisons rise to about 75,000. The work is still far below the reversed case, but it is now clearly more than n.
This table shows the rule from the earlier section in practice. The steps follow the number of inversions. With a larger k, each value can have more bigger values in front of it, and each of those costs one shift. Per value, the shifts go from about 0.09 at k = 1 to about 8.4 at k = 100.
A worked example of the cost formula
Suppose every value in a list is at most k places from its final position. Take a value v that starts at position j. A bigger value that sits in front of v must end up after v. Both values can move only k places, so the bigger value must start fewer than 2k places before v. That leaves at most 2k - 1 bigger values in front of v, so v costs at most 2k - 1 shifts.
For k = 3, each value costs at most 5 shifts. A list of length 1,000 then needs at most 5,000 shifts, and at most about 6,000 comparisons and shifts together. The exact count depends on the input, but this bound holds for every list with that property.
Compare this with a general list of length 1,000. Its shift count can be as large as 499,500, which is the count for a reversed list. The bound for the nearly sorted list is about a hundred times smaller. This is why insertion sort is worth knowing even though it is slow on general input. Many programs sort data that is almost in order, and in that case the method does close to linear work.
Big O notation is the usual way to write this. It describes how the number of steps grows when the input grows. Insertion sort is O(n squared) in the worst case, which is the reversed input. For an input where each value is at most k positions from its final place, it is O(n times k). When k is a small fixed number, this is O(n). The next section shows timing measurements that match this pattern.
Timing on one machine
Step counts are the most reliable measure, because they do not change from run to run or from one computer to another. Time is also useful, because it shows the real cost of the steps. The next program times three cases on a list of 5,000 values. Python is much slower than Java for the same loop, so the list is smaller than in the Java version of this lesson. The program runs each case seven times and reports the middle value, which is less affected by one slow run.
import random
import statistics
import time
def insertion_sort(a):
for i in range(1, len(a)):
value = a[i]
j = i - 1
while j >= 0 and a[j] > value:
a[j + 1] = a[j]
j -= 1
a[j + 1] = value
def nearly_sorted(n, swaps, max_distance, seed):
a = list(range(n))
rng = random.Random(seed)
for _ in range(swaps):
i = rng.randrange(n)
j = min(n - 1, i + 1 + rng.randrange(max_distance))
a[i], a[j] = a[j], a[i]
return a
def random_values(n, seed):
rng = random.Random(seed)
return [rng.randrange(-2**31, 2**31) for _ in range(n)]
def median_ms(task, trials):
times = []
for _ in range(trials):
start = time.perf_counter()
task()
times.append((time.perf_counter() - start) * 1000)
return statistics.median(times)
n = 5000
nearly = nearly_sorted(n, n // 10, 5, 42)
rnd = random_values(n, 99)
print(f"n = {n} (median of 7 runs)")
print(f"insertion sort, nearly sorted: {median_ms(lambda: insertion_sort(list(nearly)), 7):.2f} ms")
print(f"insertion sort, random: {median_ms(lambda: insertion_sort(list(rnd)), 7):.2f} ms")
print(f"sorted() on random: {median_ms(lambda: sorted(rnd), 7):.2f} ms")Two runs of the program on the same machine gave these results:
n = 5000 (median of 7 runs)
insertion sort, nearly sorted: 0.48 ms
insertion sort, random: 452.93 ms
sorted() on random: 0.66 msn = 5000 (median of 7 runs)
insertion sort, nearly sorted: 0.48 ms
insertion sort, random: 441.21 ms
sorted() on random: 0.51 msThe numbers will differ on another computer, and they depend on what else the machine is doing. The pattern is what matters. On nearly sorted data, insertion sort took about 0.1 percent of the time it took on random data of the same length. On random data, insertion sort was hundreds of times slower than sorted(), which uses a faster method for large inputs.
The timing run shows one more point. The nearly sorted list was built with 500 swaps, each joining positions at most 5 apart, so it has a small number of inversions. The sort finished in a fraction of a millisecond.
The lambda in each timing call is a small function with no name. lambda: insertion_sort(list(nearly)) makes a copy of the list each time, so the timing measures the sort and not the work of a previous run on the same list. Without the copy, the second run would sort an already sorted list.
Common mistakes
Assuming insertion sort is always fast because it is simple. A simple method can still be slow. On reversed input of length 8,000, the program above made about 32 million comparisons and 32 million shifts. Check the shape of the data before you choose this method.
Using >= where > is needed. If the loop shifts values that are equal to the picked value, equal values swap their order. The output is still sorted, but two equal values may come out in the wrong order from how they went in. Insertion sort keeps equal values in their original order only when the shift test uses >. The program above uses > in the loop condition.
Reading a[j] after j has become negative. The test must check j >= 0 before it reads the list. In Python this order matters in a quiet way. Here is the wrong order:
The output is:
[1, 2, 3, 4, 5, 6]No error appears, and the answer is right. The reason is that Python checks a[j] > value first, which is true for these values, and then j >= 0, which is false when j is -1, so the loop stops before it shifts anything. The mistake is still there. The test reads a[-1], which is the last value in the list, and nothing in the output shows it. In another version of this loop, where the body runs before the bounds test, the same read would change the list. The fix is to put j >= 0 first, as in while j >= 0 and a[j] > value. Python then never reads a negative index at all.
In Java, the same mistake throws an ArrayIndexOutOfBoundsException at once. Python's negative indexes make the error quiet, so reading the test order is the only safe check.
Forgetting that the picked value must be saved. The loop writes over a[i] when it shifts values, so the code must copy a[i] into a variable before the loop starts. If it does not, the value is lost. The list then ends up with a duplicate and a missing value. The check is simple: after sorting, the list must contain the same values as before. The program compares its output with sorted() to catch this.
Counting steps in the wrong place. The counts in this lesson go up inside the loop, once for each comparison and once for each shift. If a counter is placed outside the loop, it counts one step per outer loop run, and the numbers look far too small. A quick test is to compare the count for the sorted input with n - 1. The sorted case should give exactly 999 comparisons for n = 1000.
Expecting timing numbers to match a book. Times depend on the computer, the Python version and background work. Compare step counts when you want to check the method, and use timing only to see the rough size of the cost.
Practice
Try each exercise in a file first. Check your answer after you have made an attempt.
Exercise 1. Run insertion sort by hand on [2, 1, 4, 3, 6, 5]. Count the comparisons and the shifts. Use the rule from the lesson: a comparison happens each time the loop checks a value, and a shift happens each time a value moves one place right.
Show the answer
The result is [1, 2, 3, 4, 5, 6] with 7 comparisons and 3 shifts. The shifts are the three inversions in the input: 2 before 1, 4 before 3, and 6 before 5. The comparisons are 3 shifts plus 5, minus the values that went to the front, which is 1 here, so 3 + 5 - 1 = 7.
Exercise 2. A list of length 6 is in reverse order, [6, 5, 4, 3, 2, 1]. How many shifts does insertion sort make? Give the number from the formula and then check it by running the sort.
Show the answer
It makes 15 shifts. For a reversed list of length n, the number of shifts is n times n - 1 divided by 2, which is 6 times 5 divided by 2, or 15. Running the sort on this input gives 15 comparisons and 15 shifts. Every inserted value reaches the front of the list, so the loop never makes a final check that stops early.
Exercise 3. A list of length 2,000 is made by swapping neighbours in 1,000 pairs, so it looks like [2, 1, 4, 3, 6, 5, ...]. How many shifts does insertion sort make? How many comparisons?
Show the answer
It makes 1,000 shifts, one for each swapped pair, because each pair is one inversion. The comparisons are 1,000 shifts plus 1,999, minus the values that moved all the way to the front. Only the value 1 moves to the front, so the total is 1,000 + 1,999 - 1 = 2,998. A run of the same kind of program on length 2,000 gave 1,000 shifts and 2,998 comparisons, which matches.
Exercise 4. A log file has 50,000 lines sorted by time. Two hundred lines were added at the end, and each of them belongs about 10 lines earlier. Explain in plain words why insertion sort is a good choice for this file, and how many shifts to expect roughly.
Show the answer
Insertion sort is a good choice because the file is almost sorted. Only the 200 new lines are out of place. Each new line moves about 10 places to the left, so the shifts are about 200 times 10, which is 2,000. The rest of the work is one check per line, so the total is about 50,000 checks plus 2,000 shifts. This is close to one pass over the file.
Exercise 5. Change the report function in the counting program so that it also counts the inversions with a separate double loop. Predict whether the inversion count will match the shift count for each row, and say why.
Show the answer
The inversion count will match the shift count on every row. The shift count is exactly the number of inversions, because each shift removes one pair where a bigger value comes before a smaller one, and insertion sort makes no other kind of move. A double loop that compares every pair i < j with a[i] > a[j] counts those pairs directly. Running it on the rows in the output would confirm the match.
Summary
- Insertion sort grows a sorted prefix, one value at a time, by shifting bigger values to the right.
- Each shift removes one inversion, so the number of shifts equals the number of inversions in the input.
- On nearly sorted input, few inversions exist, so the work is close to the list length. On reversed input the work is about
nsquared divided by 2. - Count steps when you want a reliable measure. Times change from machine to machine, but the step counts stay the same.
- Check the bounds before reading a list index. In Python a negative index does not raise an error, so the order of the tests matters even more.
- Keep the picked value in a variable before the loop shifts anything.
The next lesson in this module, Radix sort, uses a different idea and does not depend on the order of the input.