Bubble Sort to Timsort: Why Python Ditched O(n²)

Python’s sort() is too fast to be simple

Run sorted([3,1,2]) in Python and you get [1,2,3] in microseconds. Under the hood, you’re not running the bubble sort from your algorithms textbook—you’re running Timsort, a hybrid algorithm that combines merge sort and insertion sort, exploits real-world data patterns, and routinely beats $O(n \log n)$ worst-case guarantees in practice. The gap between “sorting 101” and production code is enormous, and most people never see why.

I’m going to show you exactly what happens when you replace the beginner-friendly algorithms with what Python actually uses, and why the performance difference matters even on small datasets.

What bubble sort actually costs

Bubble sort is the first algorithm most of us learn. The idea: repeatedly step through the list, compare adjacent elements, swap if they’re out of order. After each pass, the largest unsorted element “bubbles” to its correct position.

Here’s the canonical implementation:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # Already sorted
            break
    return arr

The nested loops give you $O(n^2)$ comparisons in the worst case. Even with the swapped optimization (which shortcuts on already-sorted input), you’re still doing $\frac{n(n-1)}{2}$ comparisons for reverse-sorted data.

Let me show you the actual cost:

import random
import time

def benchmark(sort_fn, size):
    data = [random.randint(0, 10000) for _ in range(size)]
    start = time.perf_counter()
    sort_fn(data.copy())
    return (time.perf_counter() - start) * 1000  # milliseconds

for n in [100, 500, 1000, 2000]:
    ms = benchmark(bubble_sort, n)
    print(f"n={n}: {ms:.2f}ms")

On my M1 MacBook (Python 3.11):

n=100: 0.89ms
n=500: 22.14ms
n=1000: 88.76ms
n=2000: 356.41ms

Doubling the input size quadruples the time. At 10,000 elements, you’re waiting multiple seconds. This is why no production system uses bubble sort.

Why Python chose Timsort over quicksort

Most standard libraries pick quicksort ($O(n \log n)$ average, $O(n^2)$ worst) or merge sort ($O(n \log n)$ guaranteed, but needs $O(n)$ extra space). Python does neither.

In 2002, Tim Peters designed Timsort specifically for Python, and it’s since been adopted by Java, V8 (JavaScript), Swift, and Rust. The key insight: real-world data is rarely uniformly random. Lists are often partially sorted, have repeated elements, or contain sorted runs.

Timsort exploits this. Here’s the algorithm at a high level:

1. Identify natural runs: scan the array for already-sorted subsequences (ascending or descending)
2. Extend short runs: if a run is below minimum length (32-64 elements depending on $n$), use insertion sort to extend it
3. Merge runs: use a modified merge sort to combine runs, maintaining a stack invariant that ensures balanced merges

The minimum run length is chosen via $\text{minrun} = n / 2^k$ where $k$ is selected so $32 \leq \text{minrun} \leq 64$. This ensures the number of runs is close to, or slightly less than, a power of two, optimizing merge tree balance.

The insertion sort trick that makes it fast

For small subarrays (under ~64 elements), insertion sort beats merge sort due to lower overhead and better cache locality. Timsort leans into this.

Here’s Python’s insertion sort (simplified from the CPython source):

def insertion_sort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        # Binary search could be used here for the position,
        # but shifting still takes O(n), so standard insertion is fine
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Time complexity: $O(n^2)$ worst case, but $O(n)$ on nearly-sorted data (which is exactly what Timsort feeds it after identifying runs).

Benchmark on small arrays:

import random
import time

def benchmark(sort_fn, size):
    data = [random.randint(0, 10000) for _ in range(size)]
    start = time.perf_counter()
    sort_fn(data.copy())
    return (time.perf_counter() - start) * 1000

for n in [10, 20, 50]:
    ms_bubble = benchmark(bubble_sort, n)
    ms_insertion = benchmark(insertion_sort, n)
    print(f"n={n}: bubble={ms_bubble:.3f}ms, insertion={ms_insertion:.3f}ms")

n=10: bubble=0.009ms, insertion=0.006ms
n=20: bubble=0.035ms, insertion=0.020ms
n=50: bubble=0.221ms, insertion=0.115ms

Insertion sort is nearly 2x faster even at $n=50$. The constant factors matter.

Galloping mode: the hidden optimization

When Timsort merges two runs, it doesn’t blindly compare elements one by one. If one run is “winning” (contributing many consecutive elements to the merged output), Timsort switches to galloping mode.

Instead of linear search, it uses exponential search (jump ahead by powers of 2) then binary search to find where the next element from the other run should be inserted. This reduces the number of comparisons significantly when merging a small run into a large one, though the total elements copied remains $O(m + n)$.

For merging two runs $A$ and $B$ of lengths $m$ and $n$, the standard merge performs $O(m + n)$ comparisons. With galloping mode, when one run dominates, the comparison count can drop to roughly $O(m + \log n)$ or $O(\log m + n)$, depending on the data distribution.

I haven’t implemented galloping mode here (it’s gnarly), but you can see it in the CPython source. The docs claim performance improvements of 10-50% on real datasets with long runs.

Building a minimal Timsort

Here’s a stripped-down Timsort that skips galloping but keeps the core structure:

def timsort(arr):
    n = len(arr)
    if n < 2:
        return arr

    min_run = calc_min_run(n)

    # Step 1: Create sorted runs of length min_run
    for start in range(0, n, min_run):
        end = min(start + min_run - 1, n - 1)
        insertion_sort(arr, start, end)

    # Step 2: Merge runs bottom-up
    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min(start + size * 2 - 1, n - 1)
            if mid < end:
                merge(arr, start, mid, end)
        size *= 2

    return arr

def calc_min_run(n):
    """
    Returns min_run in [32, 64] such that n/min_run is close to a power of 2.
    Uses bit manipulation: r accumulates whether any 1-bits were shifted out,
    ensuring we round up when n isn't a perfect power of 2.
    """
    r = 0
    while n >= 64:
        r |= n & 1  # Track if we're losing any 1-bits
        n >>= 1
    return n + r

def merge(arr, left, mid, right):
    """Merge arr[left:mid+1] and arr[mid+1:right+1] in-place."""
    left_copy = arr[left:mid + 1]
    right_copy = arr[mid + 1:right + 1]

    i = j = 0
    k = left

    while i < len(left_copy) and j < len(right_copy):
        if left_copy[i] <= right_copy[j]:
            arr[k] = left_copy[i]
            i += 1
        else:
            arr[k] = right_copy[j]
            j += 1
        k += 1

    while i < len(left_copy):
        arr[k] = left_copy[i]
        i += 1
        k += 1

    while j < len(right_copy):
        arr[k] = right_copy[j]
        j += 1
        k += 1

This version uses insertion sort for initial runs, then bottom-up merging. It’s missing the run-detection logic (which would scan for natural ascending/descending sequences), but it’s enough to see the speedup.

Head-to-head benchmark: bubble vs Timsort vs Python’s sorted()

import random
import time

def benchmark_all(size, data_type="random"):
    if data_type == "random":
        data = [random.randint(0, 10000) for _ in range(size)]
    elif data_type == "sorted":
        data = list(range(size))
    elif data_type == "reversed":
        data = list(range(size, 0, -1))
    else:
        data = [random.randint(0, 10) for _ in range(size)]  # many duplicates

    times = {}

    start = time.perf_counter()
    bubble_sort(data.copy())
    times['bubble'] = (time.perf_counter() - start) * 1000

    start = time.perf_counter()
    timsort(data.copy())
    times['timsort'] = (time.perf_counter() - start) * 1000

    start = time.perf_counter()
    sorted(data.copy())
    times['builtin'] = (time.perf_counter() - start) * 1000

    return times

for dtype in ["random", "sorted", "reversed"]:
    print(f"\n{dtype.upper()} data (n=2000):")
    t = benchmark_all(2000, dtype)
    print(f"  Bubble: {t['bubble']:.2f}ms")
    print(f"  Timsort (minimal): {t['timsort']:.2f}ms")
    print(f"  Python sorted(): {t['builtin']:.2f}ms")

Results on my machine:

RANDOM data (n=2000):
  Bubble: 358.12ms
  Timsort (minimal): 4.23ms
  Python sorted(): 0.31ms

SORTED data (n=2000):
  Bubble: 0.18ms
  Timsort (minimal): 1.87ms
  Python sorted(): 0.02ms

REVERSED data (n=2000):
  Bubble: 361.45ms
  Timsort (minimal): 2.91ms
  Python sorted(): 0.05ms

Bubble sort is 85x slower than our minimal Timsort on random data. Python’s built-in sorted() (full Timsort in C) is another 14x faster than my Python implementation.

But look at the sorted data: bubble sort’s early-exit optimization brings it down to 0.18ms, while Python’s Timsort hits 0.02ms by recognizing the entire array as a single run. This is the adaptive behavior you don’t get from textbook merge sort.

The $O(n)$ best case nobody tells you about

Timsort’s worst-case complexity is $O(n \log n)$, same as merge sort. But the best case is $O(n)$ when the input is already sorted (or reverse-sorted, which Timsort detects and reverses in linear time).

The number of comparisons for a sorted array of length $n$ is exactly $n – 1$ (one pass to confirm it’s a single run). For merge sort, even on sorted input, you still do $O(n \log n)$ comparisons because it doesn’t check.

This adaptive behavior is why Timsort dominates on real-world data, which often has structure. If you’re sorting database query results, user input, or time-series data, you’re probably not hitting the worst case.

Where Timsort loses (and nobody admits it)

Timsort isn’t always the fastest. On truly random data with no runs, quicksort can be faster due to better cache behavior and in-place partitioning (Timsort needs $O(n)$ extra space for merging).

I ran a quick test with NumPy’s quicksort (used by np.sort(kind='quicksort')) on 100,000 random integers:

import numpy as np
import time

data = np.random.randint(0, 100000, size=100000)

# NumPy quicksort
start = time.perf_counter()
np.sort(data.copy(), kind='quicksort')
print(f"Quicksort: {(time.perf_counter() - start) * 1000:.2f}ms")

# NumPy mergesort (stable, like Timsort)
start = time.perf_counter()
np.sort(data.copy(), kind='mergesort')
print(f"Mergesort: {(time.perf_counter() - start) * 1000:.2f}ms")

# Python sorted (Timsort)
start = time.perf_counter()
sorted(data.tolist())
print(f"Timsort: {(time.perf_counter() - start) * 1000:.2f}ms")

Quicksort: 8.12ms
Mergesort: 10.45ms
Timsort: 12.33ms

Quicksort wins by ~34% here, but it’s not stable (doesn’t preserve the relative order of equal elements). Timsort guarantees stability, which matters when sorting objects by multiple keys.

Also, Timsort’s $O(n)$ space overhead can hurt on memory-constrained systems. If you’re sorting a billion-element array, that’s a billion-element temporary buffer. Quicksort does it in-place with $O(\log n)$ stack space.

Why interviewers still ask about bubble sort

If bubble sort is useless, why do coding interviews still test it?

Because the interview isn’t testing your ability to sort. It’s testing whether you can:

1. Implement a simple algorithm correctly under pressure (off-by-one errors in the inner loop are common)
2. Analyze time complexity ($O(n^2)$) and explain the $\frac{n(n-1)}{2}$ comparisons
3. Recognize when an optimization (early exit on swapped == False) changes best-case to $O(n)$
4. Know when to use a library (sorted()) vs implement from scratch

The real question is: “Can you write a nested loop without breaking it?” If you can’t do bubble sort, you probably can’t do two-pointer sliding window or backtracking either.

But once you’ve proven you can implement the basics, you should always default to the built-in sort. I’ve seen production code with hand-rolled quicksort that had a bug in the partition function (swapped the pivot comparison direction), causing $O(n^2)$ blowup on sorted input. Python’s sorted() is battle-tested across millions of codebases. Use it.

When you’d actually write your own sort (hint: almost never)

There are exactly two cases where you might implement a custom sort:

1. Educational purposes (like this post)
2. Embedded systems with <1KB RAM where you can’t afford Timsort’s space overhead and need an in-place $O(n \log n)$ like heapsort

Everywhere else, use the standard library. Even if you think you can optimize for your specific data distribution, you’re probably wrong. The CPython team has spent 20+ years tuning Timsort. You haven’t.

If you’re sorting structured data and want to avoid some comparisons, you might use a radix sort (for integers/strings) or counting sort (for small integer ranges), both of which are $O(n)$ but non-comparison-based. But Python’s sorted() with a good key function usually beats a half-baked radix sort in practice.

FAQ

Q: Why is Timsort stable when quicksort isn’t?

Stability means that elements with equal keys maintain their relative order after sorting. Timsort is stable because it’s based on merge sort, which never swaps non-adjacent elements. Quicksort, by contrast, partitions the array in-place and can move equal elements past each other. Stability matters when sorting objects by multiple fields (e.g., sort by last name, then by first name—you want the first-name order preserved within each last name).

Q: Does Python use Timsort for dict keys too?

No. Dicts are hash tables, not sorted. But if you call sorted(my_dict.keys()), that uses Timsort. As of Python 3.7+, dict insertion order is preserved (via an internal index array), but it’s not sorted order.

Q: Can I force Python to use quicksort instead of Timsort?

Not with the built-in sorted(). You’d need to use NumPy (np.sort(kind='quicksort')) or implement it yourself. But unless you have a specific reason (e.g., you’re benchmarking algorithms), there’s no point. Timsort is faster on almost all real-world data.

The verdict: just call sorted()

If you’re writing Python and manually implementing any $O(n \log n)$ sort, you’re doing it wrong. Use sorted() for lists, list.sort() for in-place sorting, and move on.

Timsort is a masterclass in pragmatic algorithm design. It doesn’t chase theoretical purity—it bends the rules to fit real-world data. Natural runs, insertion sort for small subarrays, galloping mode for unbalanced merges—all of these are “hacks” that wouldn’t appear in a textbook proof, but they work.

The lesson isn’t “memorize Timsort.” It’s “understand the gap between asymptotic complexity and real performance.” An $O(n^2)$ algorithm with a tiny constant can beat an $O(n \log n)$ algorithm with high overhead (see: insertion sort vs merge sort on $n < 50$). A stable sort can matter more than raw speed. And exploiting data structure—like Timsort does with runs—can drop you from $O(n \log n)$ to $O(n)$ in practice.

The minrun choice of 32-64 was tuned empirically to balance insertion sort overhead against merge tree depth. While hardware has evolved since 2002, the core tradeoffs remain valid—insertion sort’s simplicity wins for small arrays regardless of exact cache sizes, and the merge count optimization from keeping runs near powers of two is architecture-independent.