Bubble sort and insertion sort in Python, step by step

Bubble sort walks along a list comparing neighbours and swapping any pair that's out of order, and each pass carries the biggest remaining item to the end. Insertion sort takes the items one at a time and slides each one left until it fits, the way most people sort a hand of cards. Both are six lines of Python, and both are O(n²) on average: on a random list, double the data and the work goes up four times. In this post we trace both by hand on five numbers, write them in Python, catch the classic mistakes, and count every comparison to see why a full spreadsheet would take bubble sort 549,755,289,600 of them.

This post goes with letsBug Code, episode 2. Watch it first, or read on: everything in the video is here, plus the counting code, a side-by-side table and a challenge.

Sorting a million rows

Open a spreadsheet, pick a column and click Sort A to Z. Your contacts, a game's leaderboard, your emails by date: all of them are sorted by a program. A full Excel sheet holds 1,048,576 rows. That's 2²⁰, just over a million: the number behind the binary search post, where a million sorted items took at most 20 checks to search. But that list had to be sorted first. How?

Before we start, a prediction. Suppose a simple sort takes 1 second to sort 1,000 numbers. How long does it take for 2,000? The tempting answer is 2 seconds: double the data, double the work. Hold on to your answer; we come back to it below.

Bubble sort: the idea

Here are five numbers: 7, 3, 9, 2, 5. Bubble sort walks along the list comparing neighbours. If the left one is bigger, they swap. Then it moves one step right and compares the next pair. One full walk along the list is called a pass.

On every pass, the biggest number not yet in place gets carried to the end, like a bubble rising to the top. That's where the name comes from.

Tracing pass 1

Let's trace the first pass, one comparison at a time. i is the position of the left number in each pair:

That's 4 comparisons and 3 swaps. The 9 has reached the end, its final place, and it never moves again. Notice row 1: nothing changed, but it's still a row in the trace. Skipping the "no change" rows is an easy way to lose track.

The other passes: 10 comparisons

Here's the classic slip: writing the list after one pass as if it's sorted. It isn't. After pass 1 we have 3, 7, 2, 5, 9, and only the 9 is in its final place. So we keep going, and each pass is one comparison shorter, because the end of the list is already done:

After pass 3 the list is already sorted. But the code can't see that, so pass 4 still makes one more comparison. Add them up: 4 + 3 + 2 + 1 = 10 comparisons for five numbers, and 3 + 2 + 1 = 6 swaps.

Bubble sort in Python

def bubble_sort(items):
    n = len(items)
    for end in range(n - 1, 0, -1):
        for i in range(end):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]

numbers = [7, 3, 9, 2, 5]
bubble_sort(numbers)
print(numbers)  # [2, 3, 5, 7, 9]

Line by line:

• end is the last position each pass reaches: 4, then 3, 2 and 1 for our five numbers. range(n - 1, 0, -1) counts down and stops before 0.
• The inner loop walks i from 0 up to end - 1, so it compares items[i] with items[i + 1], ending at the pair items[end - 1] and items[end].
• If the pair is out of order, a, b = b, a swaps them in one line. Python builds the right-hand side first, so no temporary variable is needed.
• It sorts the list in place: it changes numbers itself and returns nothing.

The classic bug: range(n)

Let the inner loop run over the whole list and it breaks on the very first pass:

def bubble_sort_buggy(items):
    n = len(items)
    for end in range(n - 1, 0, -1):
        for i in range(n):  # the bug: should be range(end)
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]

bubble_sort_buggy([7, 3, 9, 2, 5])
# IndexError: list index out of range

On the last step i is 4, so i + 1 is 5, one past the end of a five-item list. That's why the inner range stops one short. range(n - 1) would also avoid the crash, but it keeps re-checking the finished end of the list on every pass. range(end) skips it.

Insertion sort: like sorting a hand of cards

Pick up playing cards one at a time and you probably slide each new card left until it sits in the right place. That's insertion sort. The left part of the list is always sorted. Take the next item and slide it left past every bigger item until it fits.

Same five numbers, 7, 3, 9, 2, 5. The 7 on its own is our sorted part to start with:

That's 1 + 1 + 3 + 3 = 8 comparisons, two fewer than bubble sort. Count the comparison that stops a slide too: in step 4, "is 3 bigger than 5?" is a real comparison, and the answer "no" is what tells the 5 to stop. The swaps are 1 + 0 + 3 + 2 = 6, exactly the same as bubble sort's.

Insertion sort in Python

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

numbers = [7, 3, 9, 2, 5]
insertion_sort(numbers)
print(numbers)  # [2, 3, 5, 7, 9]

• i is the item we're placing. It starts at 1, because one item on its own is already sorted.
• j is where that item is right now. It starts at i and moves left as the item slides.
• The while keeps going while there's something to the left (j > 0) and that something is bigger.
• Each step swaps the item one place left and moves j with it.
• As soon as the item to the left is smaller or equal, the loop stops early. That's why a list that's already sorted takes only one comparison per item: n − 1 in total.

Bubble sort vs insertion sort

Both sorts swap only neighbours that are out of order, and every such swap fixes exactly one out-of-order pair. So they always make the same number of swaps: one per pair that starts in the wrong order (7, 3, 9, 2, 5 has six such pairs). The difference is how many comparisons they waste finding them:

So insertion sort usually wins: on random data it makes about half the comparisons, and on a list that's nearly sorted it's close to one pass. That's why insertion sort, not bubble sort, is the simple sort that real libraries, Python's included, still use on small pieces. Both stay stable only because they swap on >. Change it to >= and equal items start swapping past each other.

Counting comparisons: why it's O(n²)

On n items, bubble sort's first pass makes n − 1 comparisons, the next n − 2, and so on down to 1. Stack those rows up and you get a triangle, about half of an n by n square:

(n − 1) + (n − 2) + … + 2 + 1 = n(n − 1)/2

For our five numbers that's 5 × 4 / 2 = 10, just like the trace. Insertion sort on a reversed list hits the same total, because every item has to slide all the way to the front.

Now back to your prediction. Double the list, and the triangle gets twice as wide and twice as tall: four times the work, not two. So if 1,000 numbers take 1 second, 2,000 take about 4 seconds. And a million numbers have a thousand times more items, so about a million times more work: a million seconds, or about 11.6 days. Programmers write this growth as O(n²).

Count them yourself

You don't have to trust the table. Wrap each number in a small class that counts every time it's compared, then run the real sort functions on it. Run this after the two functions above:

class Counted:
    """A number that counts every comparison made on it."""
    comparisons = 0

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

    def __gt__(self, other):
        Counted.comparisons += 1
        return self.value > other.value

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


def count(sort, values):
    Counted.comparisons = 0
    sort([Counted(v) for v in values])
    return Counted.comparisons


print(count(bubble_sort, [7, 3, 9, 2, 5]))        # 10
print(count(insertion_sort, [7, 3, 9, 2, 5]))     # 8
print(count(insertion_sort, range(1000)))         # 999: already sorted
print(count(insertion_sort, range(1000, 0, -1)))  # 499500: reversed
print(count(bubble_sort, range(1000)))            # 499500: even when sorted

Python calls __gt__ whenever it evaluates a > b, so every comparison inside the sort goes through our counter. Our two sorts only use >; __lt__ is there for Python's own sort, which uses <.

How real sorts are fast

So how does a spreadsheet sort a million rows without waiting days? Not like this. Let's count Python's built-in sort on a full column of random numbers with the same count function:

import random

rng = random.Random(1)
rows = [rng.random() for _ in range(1_048_576)]
print(count(sorted, rows))       # 19651111
print(1_048_576 * 1_048_575 // 2)  # 549755289600: bubble sort, the same rows

About 20 million comparisons against 550 billion: roughly 28,000 times fewer. (We ran it on Python 3.13; another version may give a slightly different count.) That's close to n × log₂(n) = 1,048,576 × 20 = 20,971,520. Practical sorts grow like this, written O(n log n): double the data and the work only a little more than doubles.

Python's sort, called Timsort, is built on merging. It walks the list looking for stretches that are already in order, called runs, and merges them together, which is much cheaper than comparing everything with everything. We'll build merge sort ourselves later in the series.

But the slow sorts aren't useless. When a run is too short, Python's sort lengthens it with binary insertion sort: insertion sort that finds each item's place with a binary search instead of sliding one step at a time. And if the whole list has fewer than 64 items, it finds the first run and binary-insertion-sorts the rest into it. On a few items, insertion sort is hard to beat.

Bubble sort has no such job. Wikipedia sums up why: other simple sorts like insertion sort "generally run faster than bubble sort, and are no more complex". Donald Knuth wrote that it "seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems". And in 2007, when Google's then CEO Eric Schmidt asked presidential candidate Barack Obama the best way to sort a million integers, Obama answered: "I think the bubble sort would be the wrong way to go."

def bubble_sort_early_exit(items):
    n = len(items)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:
            break  # a pass with no swaps: the list is sorted

print(count(bubble_sort_early_exit, range(1000)))      # 999
print(count(bubble_sort_early_exit, [7, 3, 9, 2, 5]))  # 10

a = [3, 1, 2]
b = a
a.sort()
print(b)  # [1, 2, 3]: b is the same list as a

c = [3, 1, 2]
d = sorted(c)
print(c, d)  # [3, 1, 2] [1, 2, 3]

Keep going

• Watch the full lesson, Bubble Sort and Insertion Sort in Python, Explained, and the rest of the letsBug Code series on YouTube.
• Once a list is sorted, you can search a million items in 20 checks: binary search in JavaScript and Python, letsBug Code episode 1.
• Need only the biggest item, not a sorted list? One pass does it: largest and smallest number in an array, without sorting at all.
• The same sorts in C and JavaScript, plus merge sort and quick sort: sorting algorithms in C and JavaScript.

Sources

• Microsoft: Excel specifications and limits (1,048,576 rows)
• Python documentation: Sorting Techniques (sort vs sorted, stability, Timsort)
• CPython source: listsort.txt, how Python's list sort works (runs, merging, binary insertion sort)
• Wikipedia: Bubble sort (complexity, the Knuth and Obama quotes)
• Wikipedia: Insertion sort (best and worst cases, sorting a hand of cards)
• University of San Francisco: comparison sorting, visualised (watch both sorts step by step)

Every code sample in this post was run in Python 3.13 before publishing.