Kids lining up by height
Bubble Sort
The analogy
Walk down a line of kids and only ever compare two side by side. If the left one is taller, they trade places. One full sweep pushes the tallest kid all the way to the back — like a bubble floating up. Sweep again and again until nobody needs to move.
Visualizer
Watch it sort
step 1 / 575
3
8
1
9
2
7
4
8 numbers, out of order. Press play — or step through one comparison at a time.
📖 In depth — the full reference
The sorting scoreboard (for reference across all five sorting lessons)
| algorithm | best | average | worst | extra space | stable? |
|---|---|---|---|---|---|
| bubble | O(n) with early exit | O(n²) | O(n²) | O(1) | yes |
| selection | O(n²) — always | O(n²) | O(n²) | O(1) | no (long-range swaps) |
| insertion | O(n) on sorted input | O(n²) | O(n²) | O(1) | yes |
| merge | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| quick | O(n log n) | O(n log n) | O(n²) (bad pivots) | O(log n) stack | no (typical) |
| Timsort (stdlib) | O(n) | O(n log n) | O(n log n) | O(n) | yes |
Bubble sort — everything worth knowing
- Invariant: after pass k, the k largest values sit in their FINAL slots at the right end — each pass can therefore stop one slot earlier.
- Stable: equal values never jump over each other, because only ADJACENT out-of-order pairs swap.
- "Stable" matters when values carry luggage: sort orders by price after sorting by date, and equal-priced orders stay date-ordered — only a stable sort promises that.
- The early-exit flag (no swaps in a pass → done) is what makes the best case O(n): one clean pass over already-sorted input.
- Nobody ships bubble sort — it exists to teach invariants, swaps and O(n²). Knowing WHY it loses to insertion sort (it moves elements one lazy step per pass) is the actual lesson.
What Python actually uses
- sorted(xs) returns a new sorted list; xs.sort() sorts in place. Both are Timsort: stable, O(n log n) worst case, O(n) on already-sorted or reversed runs.
- Sort by anything with key=: sorted(words, key=len), sorted(orders, key=lambda o: o.price). The key function runs ONCE per element.
- reverse=True beats sorting then reversing. For "largest 3", heapq.nlargest(3, xs) skips sorting entirely — O(n log 3).
- Timsort was invented FOR Python (Tim Peters, 2002) by hunting the runs already present in real data — merge sort's strategy plus insertion sort's manners.
def bubble_sort(a):
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
return a # early exit -> O(n)
return aCheck yourself
What does one full pass of bubble sort guarantee?
Practice — write it yourself
bubble_sort(arr) returns a sorted copy using adjacent compare-and-swap passes. Bonus honesty: add the early exit when a pass makes no swaps. (No sorted() allowed!)
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser