Bubble Sort Explained Visually: Why It's O(n²)

Bubble sort is the first sorting algorithm most people meet and the first one they are told never to use. Both halves of that are true, and neither is why it keeps showing up in interviews. It shows up because it is the smallest complete comparison sort there is: two nested loops, one swap, and a running time you can derive out loud in under a minute.

The problem it solves

You have values in no particular order and you need them ascending. You may compare two values and you may swap two values. Nothing else.

Bubble sort is the most literal possible answer. If two neighbours are in the wrong order, put them in the right order. Keep going until there is nothing left to fix.

That last clause is the entire algorithm, and it is also the reason it is slow. Repairing a list one adjacent swap at a time means a value that belongs at the far end has to be carried there one position at a time.

The intuition

Walk left to right across the list comparing each pair of neighbours, swapping whenever the left one is larger.

By the time you reach the right-hand end, the largest value is sitting there. It has to be: every comparison it took part in, it won, and every win moved it one step right. Nothing could stop it, because nothing is bigger.

So one full pass guarantees exactly one thing — the last position is now correct. Run the same pass over the first n-1 positions and the second largest settles. The sorted region grows from the right, one element per pass, which is why n-1 passes finish the job.

Read that guarantee carefully, because interviewers ask about it: a pass sorts one element, not the list.

Watch it run

Step through it below. Coral is the pair being compared right now; violet is the settled region on the right, which the algorithm never touches again.

Two things are worth pausing on. The tallest bar moves on almost every comparison until it reaches the end — that is the "bubbling". And a small value sitting near the right-hand end crawls left by exactly one position per pass, no matter how many passes it takes. That second case is the worst case, drawn.

The code

def bubble_sort(nums):
    n = len(nums)
    comparisons = swaps = 0
    for end in range(n - 1, 0, -1):        # shrinking unsorted region
        swapped = False
        for i in range(end):
            comparisons += 1
            if nums[i] > nums[i + 1]:      # strictly greater keeps ties put
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                swaps += 1
                swapped = True
        if not swapped:                    # a clean pass means it is sorted
            break
    return nums, comparisons, swaps

print(bubble_sort([5, 1, 4, 2, 8]))   # ([1, 2, 4, 5, 8], 9, 4)
print(bubble_sort([1, 2, 3, 4, 5]))   # ([1, 2, 3, 4, 5], 4, 0)
print(bubble_sort([5, 4, 3, 2, 1]))   # ([1, 2, 3, 4, 5], 10, 10)

The counters are not decoration. They are how you check the complexity claim instead of asserting it.

Why it is O(n²)

The inner loop runs end times, and end counts down from n-1 to 1. Total comparisons are therefore (n-1) + (n-2) + ... + 1, which is n(n-1)/2.

For n = 5 that is 10, and the reversed list above did exactly 10 comparisons and 10 swaps. Reverse twenty values instead and it does 190. Four times the input, nineteen times the work — that curve is what O(n²) means in practice, with the n²/2 - n/2 flattened to its dominant term.

Two more numbers for the same function:

• Best case, with the flag: O(n). An already-sorted list completes one clean pass — 4 comparisons above, 0 swaps — and the swapped check stops it there. Without that flag the best case is quadratic too, and the whole point of the optimisation is gone.
• Space: O(1). Every swap happens in the array. Nothing is allocated, which is genuinely the algorithm's one advantage.

Where it goes wrong

The big one is choosing it at all. Bubble sort is the right answer when the list is tiny or already nearly sorted and you need constant extra space. Anything else and you want merge sort or quick sort — and knowing when to say that is part of what the question is testing.

How to say it in an interview

Say the guarantee before you say the loops. Something close to this:

"Each pass walks the unsorted prefix swapping out-of-order neighbours, so after a pass the largest remaining value is at the end of that prefix. Repeat on the shrinking prefix. That is n passes over up to n elements, so O(n²) time and O(1) space. I track a swap flag so an already-sorted input costs one pass, O(n). It is stable because I only swap on a strict greater-than. In production I would sort with the library — this is here because the pattern, shrinking a region until it is empty, is the same pattern as selection and insertion sort."

That answer states the invariant, the cost, the best case, the stability and the judgement. It takes about twenty seconds, which is roughly how much time bubble sort deserves.