Bubble Sort

Bubble sort puts a list in order by comparing neighbouring items and swapping any pair that is the wrong way round, over and over, until nothing needs to move. It is rarely the right choice in real code, but it is the clearest way to see what every sorting algorithm is really doing: comparing, swapping and paying for each step.

The core idea

Bubble sort only ever looks at two items that sit next to each other. For each neighbouring pair, from the front of the list to the back, it asks one question: is the left item bigger than the right one? If it is, the two swap places. If not, they stay put. Then it moves one position along and asks again.

One trip from the front to the back is called a pass. A single pass rarely sorts the whole list, so bubble sort keeps making passes until the list is in order.

The name comes from what a pass does to the largest item. Once the largest value is part of a comparison, it wins every comparison after that, so it is swapped one step to the right, then another, then another, until it reaches the end. It 'bubbles up' to the top, just as the biggest can did in the video.

One pass, step by step

Take the list [5, 1, 4, 2]. Here is the first pass, one comparison at a time:

After this pass the list is [1, 4, 2, 5]. It isn't sorted yet, but one thing is now certain: 5, the largest value, is in its final position and will never move again.

The second pass works on [1, 4, 2] only. It compares 1 and 4 (no swap), then 4 and 2 (swap), giving [1, 2, 4, 5]. Now 4 is fixed as well. A third pass compares 1 and 2, finds nothing to swap, and the sort is done.

Knowing when to stop

Two facts decide how many passes bubble sort needs.

• Each pass fixes one more item at the end. After the first pass the largest item is in place, after the second the two largest are, and so on. So a list of n items needs at most n - 1 passes, and each pass can stop one position earlier than the one before it.
• A pass with no swaps means the list is sorted. If every neighbouring pair is already in order, the whole list is in order. There is no point making another pass.

The second fact is the 'until no swaps happen' rule from the video, and it matters more than it looks. Without it, bubble sort makes every pass even on a list that was sorted from the start. With it, a sorted list costs one pass and no swaps.

Bubble sort in Python

Here is a version that uses both ideas: a shrinking range and an early exit.

def bubble_sort(items):
    n = len(items)
    for end in range(n - 1, 0, -1):
        swapped = False
        for j in range(end):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = (
                    items[j + 1],
                    items[j],
                )
                swapped = True
        if not swapped:
            break
    return items
 
print(bubble_sort([5, 1, 4, 2]))  # [1, 2, 4, 5]

The outer loop counts end down from the last index. The inner loop walks j from the front up to, but not including, end, so items[j + 1] never runs past the unsorted part. The swapped flag starts each pass as False and flips to True on any swap; if it is still False when the pass ends, the function stops early.

The sort happens in place: it rearranges the list it was given rather than building a new one, so it needs only a couple of extra variables however long the list is.

How slow is it?

Count the comparisons in the worst case. The first pass makes n - 1 of them, the next n - 2, and so on down to 1. That adds up to n × (n - 1) / 2, roughly half of n squared. In Big O notation, bubble sort is O(n²) in the worst and average case.

Squared growth is what makes it 'terrible for big piles of tuna'. Double the list and the work roughly quadruples:

The best case is a list that is already sorted. With the early exit, that is one pass of n - 1 comparisons and no swaps, so O(n). Without the early exit, even a sorted list costs O(n²).

The number of swaps depends on how scrambled the list is. Every swap fixes exactly one pair of items that were the wrong way round, so a reversed list needs the most swaps and a sorted list needs none.

Rabbits and turtles

Large values near the start move quickly: one can travel all the way to the end in a single pass. These are sometimes called 'rabbits'. Small values near the end are 'turtles': they can move only one step to the left per pass. In [2, 3, 4, 5, 1], the 1 needs four passes to crawl to the front, even though the rest of the list was already in order. A variant called cocktail shaker sort passes left to right and then right to left, so turtles move quickly too, but it is still O(n²).

Stable by default

Bubble sort only swaps when the left item is strictly bigger. Two equal items are never swapped, so they keep the order they started in. That property is called stability, and it matters when you sort records by one field: sort people by age, and two people of the same age stay in their original order.

When to use it

In production code, almost never. Your language's built-in sort (sorted() in Python, Array.prototype.sort() in JavaScript, List.Sort() in C#) runs in O(n log n) time, is well tested and far faster on anything but tiny inputs. Reach for that first.

Bubble sort still earns its place in a few spots:

• Learning. It is the easiest sorting algorithm to trace by hand, which makes it a good way to learn about passes, loop bounds, in-place swaps and Big O.
• Very small lists. For a handful of items, simple code can be fine, though insertion sort is usually the better simple choice.
• Checking for order. One pass with no swaps proves a list is sorted, which is a neat idea to recognise even if you use it elsewhere.

It helps to see where it sits among its neighbours. Insertion sort and selection sort are also O(n²), but insertion sort is usually faster in practice, especially on nearly sorted data, and selection sort makes far fewer swaps. Merge sort and quicksort split the problem into halves and reach O(n log n), which is why they, or hybrids built on them, sit behind most real sort functions.

Common mistakes

• Running off the end. The inner loop compares items[j] with items[j + 1], so j must stop one before the last index. Looping over the whole list raises an IndexError in Python, or reads past the array in other languages.
• Using >= instead of >. Swapping equal items does extra work and breaks stability. Worse, if you loop 'until no swaps happen', two equal neighbours will swap back and forth forever.
• Forgetting the early exit. The sort still works, but a sorted or nearly sorted list pays the full O(n²) cost.
• Not shrinking the range. Comparing against the items already fixed at the end is correct but wasted effort.
• Swapping with a lost value. In languages without tuple assignment, write the first value into a temporary variable before you overwrite it.

Key takeaways

• Bubble sort compares neighbouring items and swaps any pair in the wrong order.
• Each pass carries the largest remaining item to the end, so the sorted part grows from the back.
• Stop as soon as a pass makes no swaps: a sorted list then costs a single pass.
• It is O(n²) in the worst and average case, so use a built-in O(n log n) sort for real data.
• It sorts in place and is stable, as long as you swap only when the left item is strictly bigger.