Bubble, Insertion & Selection Sort

Pick up a hand of playing cards and put them in order without thinking about how.

You almost certainly take each new card, slide it leftward past the cards bigger than it, and drop it into place — keeping the cards you have already arranged in order the whole time. That is insertion sort, the most natural sorting method humans use, and one of three O(n²) classics worth knowing cold.

None of these three will ever sort big data in your production code. But they show the cost model more plainly than anything else: how many comparisons does it take to discover the right order, and how many swaps to put things there? Every fast sort you will ever meet — merge sort, quicksort, Timsort — is an attempt to shrink those two numbers.

Three ways to think about it

Bubble sort — walk the array and swap any neighbouring pair that is out of order. Each full pass floats the largest unsorted value up to its final spot, like a bubble rising. One pass, one element settled.

Insertion sort — treat the left part as a sorted hand that grows. Take the next card and walk it left until it sits in the right place. The hand is in order at every moment.

Selection sort — scan the unsorted part for the smallest value, then swap it to the front. One scan settles one element, and it costs exactly one swap each time — but the scan itself never gets shorter.

Let us watch insertion sort build its sorted hand on four cards, [7, 3, 5, 2]:

Why all three are O(n²)

Each one has an outer loop that runs about n times, and inside it a second loop that, on average, also runs proportional to n. The comparisons pile up like the area of a triangle under the line n — roughly n²/2 of them for n elements.

The big-O class is the same for all three. What differs is the constant, and that is exactly why insertion sort is the one that survives in real code while the other two stay teaching tools.

Making the cost visible

The surest way to feel the cost is to count it. The insertion sort below keeps a tally of every comparison it makes, and we run it on the two extremes — an already-sorted list and its reverse:

def insertion_sort(arr):
    a = arr[:]               # work on a copy
    comparisons = 0
    for i in range(1, len(a)):
        j = i
        while j > 0:
            comparisons += 1
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                j -= 1
            else:
                break        # a[j] has found its place
    return a, comparisons

for case in [list(range(1, 13)), list(range(12, 0, -1))]:
    _, comps = insertion_sort(case)
    print(case[0], "...", case[-1], "→", comps, "comparisons")

1 ... 12 → 11 comparisons
12 ... 1 → 66 comparisons

Eleven against sixty-six, for the same twelve numbers. When the list is already sorted, each card checks the one to its left, sees it is smaller, and stops — that is one comparison per card, n - 1 in total, the O(n) best case. When the list is reversed, each card has to walk all the way to the front: 1 + 2 + … + 11 = 66, the O(n²) worst case laid bare.

You read their fingerprint everywhere

You will rarely write these. But the moment you see a loop scanning an array inside another loop, the instinct “that is probably O(n²) — could a sort or a hash map remove the inner loop?” should fire. That instinct is built by understanding why these three look the way they do.

The broader lesson is that every algorithm has a cost model — its dominant operation and how many times that operation runs. Elementary sorts make the model transparent because there is nowhere for the cost to hide.

Practice