Bubble Sort in Python

Bubble Sort is the canonical "first sort" — the algorithm everyone meets on day one. 🛁 It's a comparison sort (sorts by comparing pairs), an in-place sort (no extra array), and a stable sort (equal elements keep their relative order). It's also, famously, an O(n^2) sort — exactly why it's a teaching tool, not a production tool.

The name comes from how large values appear to bubble to the end of the list, one position per pass. 🫧 Each pass walks left-to-right comparing neighbours and swaps when the left one is bigger. After pass 1 the biggest element is in place; after n - 1 passes the list is sorted.

How It Works

Let's trace it on a small array: [5, 3, 8, 1, 2] (n = 5).

Pass 1 (compare every adjacent pair from index 0 to n-2):

After pass 1, `8` has bubbled to the end — we never touch that slot again.

Pass 2 (scan only up to index n-3):

Now `5` is in place too.

Pass 3: 3 > 1 → [1, 3, 2, 5, 8]; 3 > 2 → [1, 2, 3, 5, 8].

Pass 4: 1 < 2, no swaps. Done! That "zero swaps in a whole pass" signal is the key to the optimised version below.

The inner loop range shrinks each pass. After i passes, the last i slots are guaranteed correct — that's why we use range(0, n - i - 1) and not range(0, n - 1). Forgetting that shrink is the #1 bubble sort bug.

The Optimised Version

The plain version always does n - 1 full passes, even on a list that's already sorted. The optimised bubble sort adds a boolean flag, swapped, set to True whenever a pass actually swaps. If a whole pass finishes with swapped still False, the list is sorted and we break out immediately.

This cuts the best case from O(n^2) to O(n) — one pass with zero swaps confirms sortedness and exits. For nearly-sorted data (a long list with one item at the wrong end), the optimised version finishes in a few passes instead of grinding through n - 1. Worst and average cases stay O(n^2) — the flag can't save you from a fully-reversed list — but for almost-sorted input it's a real win.

Complexity Analysis

The O(1) space is auxiliary memory — we sort the list itself, not a copy. The stability comes from the > comparison: we only swap when the left is strictly greater, so equal elements never change order.

Bubble Sort vs Other Simple Sorts

Bubble, selection, and insertion sort are all O(n^2) comparison sorts everyone learns first — but they're not equal in practice.

Insertion sort almost always beats bubble sort on real data — it shifts elements instead of swapping pairs, so it does fewer writes. That's why CPython's Timsort uses insertion sort (not bubble sort) for small sub-arrays. Bubble sort's only real edge is conceptual simplicity.

Common Pitfalls

When (If Ever) to Use It

Why Production Code Doesn't Use It

Python's built-in list.sort() and sorted() are powered by Timsort, a hybrid of merge sort and insertion sort designed by Tim Peters in 2002. Timsort is O(n log n) worst case, O(n) best case, stable, and adaptive — it detects and exploits runs of already-sorted data. On real-world inputs it's dramatically faster than its worst-case bound suggests.

Unless you're writing the algorithm for a class, a code-golf bit, or a deliberate teaching example, just use `sorted(my_list)` or `my_list.sort()`. You will not write a faster sort than Timsort. 😉

Frequently Asked Questions

Is bubble sort stable?

Yes. Because we only swap when arr[j] > arr[j + 1] (strictly greater), equal elements never swap, so they keep their original relative order. That makes bubble sort a stable sort — useful when sorting records by one key while preserving a previous ordering on another.

Why is it called bubble sort?

Because on each pass the largest unsorted element rises all the way to the right — like a bubble of air surfacing in water.

Is bubble sort ever the best choice?

Almost never in production. Insertion sort beats it on small arrays; Timsort beats it on everything else. Its niche is teaching.

What's the difference between bubble sort and exchange sort?

"Exchange sort" is a broader family — any algorithm that repeatedly swaps out-of-order pairs. Bubble sort is the most famous member, but it only compares adjacent pairs.

How does Python's built-in sort compare?

It's not close. sorted() uses Timsort at O(n log n). On 10,000 random integers Timsort takes milliseconds; bubble sort takes seconds. On a million items the gap is hours vs milliseconds.

Can I write bubble sort recursively?

Yes — each recursive call does one pass, then calls itself on arr[:n-1]. Fun exercise, zero performance benefit, and adds stack overhead, so the iterative version is what textbooks and interviews use.