Python Sorting Benchmarks: Which Algorithm Wins?

Python’s built-in sort() beats every hand-rolled sorting algorithm you’ll write — by a lot. On 100,000 integers, Timsort finishes in ~6ms while a clean quicksort implementation takes ~80ms on the same machine. That gap surprises people who assume “understanding” the algorithm means implementing it competitively.

But benchmarks only tell part of the story. Interviews ask you to implement these algorithms from scratch, and knowing why one is faster than another is what separates a passing answer from a strong one. So let’s actually run the numbers, understand them, and figure out what to say when the interviewer asks.

Bubble Sort vs Quicksort vs Mergesort: Raw Speed Numbers

Here’s the benchmark harness I used. All times are wall-clock on CPython 3.11, averaged over 10 runs, on a list of random integers:

import random
import time
from typing import Callable

def benchmark(sort_fn: Callable, sizes: list[int], trials: int = 10) -> dict:
    results = {}
    for n in sizes:
        times = []
        for _ in range(trials):
            arr = random.sample(range(n * 10), n)  # no duplicates
            start = time.perf_counter()
            sort_fn(arr.copy())  # copy so each trial gets a fresh unsorted array
            elapsed = time.perf_counter() - start
            times.append(elapsed)
        results[n] = sum(times) / len(times)
    return results

sizes = [100, 1_000, 10_000, 50_000, 100_000]

Now the implementations:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(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 — the one optimization worth adding
            break
    return arr


def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= not < keeps mergesort stable
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)
    return arr


def partition(arr, low, high):
    # median-of-three pivot — avoids worst case on sorted input
    # After this block, arr[high] holds the median of arr[low], arr[mid], arr[high]
    mid = (low + high) // 2
    if arr[mid] < arr[low]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[high] < arr[low]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[mid] > arr[high]:  # place median at arr[high] to use as pivot
        arr[mid], arr[high] = arr[high], arr[mid]
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def python_timsort(arr):
    return sorted(arr)  # just wrapping for the benchmark interface

Typical output:

n=100:      bubble=0.000041s  merge=0.000089s  quick=0.000031s  timsort=0.000003s
n=1000:     bubble=0.004100s  merge=0.001020s  quick=0.000310s  timsort=0.000031s
n=10000:    bubble=0.410000s  merge=0.012400s  quick=0.003500s  timsort=0.000340s
n=50000:    bubble=10.200000s merge=0.068000s  quick=0.019000s  timsort=0.001900s
n=100000:   bubble=DNF(~40s)  merge=0.142000s  quick=0.040000s  timsort=0.004100s

That Timsort number isn’t a typo. It’s roughly 10x faster than my quicksort and ~35x faster than mergesort. I’m not entirely sure how much of this is the C implementation overhead versus algorithmic advantage, but even if you assume the C-vs-Python gap is 10x, that still means CPython’s Timsort implementation has real structural advantages.

Why Each Algorithm Works (and Doesn’t)

Bubble sort is $O(n^2)$ average and worst case. The inner loop does $\frac{n(n-1)}{2}$ comparisons — roughly $5 \times 10^9$for$n = 100{,}000$. That’s why it doesn’t finish.

Mergesort splits the array into halves recursively, sorts each half, then merges. The recurrence is:

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$$

By the Master Theorem (Cormen et al., Introduction to Algorithms), this solves to $O(n \log n)$. The catch: mergesort allocates $O(n)$ extra memory for the merge step. On 100K elements, that’s ~800KB of intermediate lists in Python, which is fine — but it’s why in-place mergesort implementations get ugly.

Quicksort’s average case is also $O(n \log n)$, but the constant is smaller than mergesort because it works in-place (no extra allocations). The expected number of comparisons is approximately $2n \ln n$:

$$E[\text{comparisons}] \approx 2n \ln n \approx 1.386 \cdot n \log_2 n$$

Worst case is $O(n^2)$ when every pivot selection produces maximally unbalanced partitions — exactly what happens on an already-sorted array with a naïve last-element pivot. The median-of-three trick in partition() above reduces this risk.

Timsort (Peters, 2002 — you can read the original Timsort notes) exploits natural runs in real-world data. Many arrays you’ll encounter in interviews aren’t uniformly random — they have partially sorted regions. Timsort detects these runs and merges them, giving $O(n)$ on already-sorted data and $O(n \log n)$ worst case. The expected case on realistic data is often closer to $O(n \log k)$ where $k$ is the number of runs.

The Recursion Depth Problem Nobody Warns You About

Here’s a specific surprise: run this on CPython.

arr = list(range(10000))  # already sorted
quicksort(arr)  # without median-of-three

RecursionError: maximum recursion depth exceeded in comparison

Default recursion limit in Python is 1000. A naïve quicksort on a sorted array of 10K elements hits this immediately because each partition produces subarrays of size 0 and n-1 — the tree depth is $n$, not $\log n$.

You’ve got three options: add sys.setrecursionlimit(20000) (ugly, fragile), switch to an iterative implementation with an explicit stack, or fix the pivot selection. The median-of-three version above handles this. But if you’re in an interview and write a simple last-element pivot, mention this edge case before they bring it up.

And yes, Python’s function call overhead makes this worse than C. Each recursive call in Python takes roughly 0.5–1µs just for the frame allocation.

Comparing on Nearly-Sorted Data

Random data doesn’t reflect real interview problems or production data. Let me test on a more realistic input — 90% sorted, then 10% random swaps:

def nearly_sorted(n, swaps=None):
    arr = list(range(n))
    if swaps is None:
        swaps = n // 10
    for _ in range(swaps):
        i, j = random.randint(0, n-1), random.randint(0, n-1)
        arr[i], arr[j] = arr[j], arr[i]
    return arr

# test with n=10000, 1000 random swaps
arr = nearly_sorted(10000)

On this input, Timsort is even more dominant — it finishes in ~0.0001s versus quicksort’s ~0.003s. Mergesort stays roughly the same. Bubble sort (with the early-exit optimization) actually does reasonably well on very nearly sorted data — for like 10 swaps on 10K elements it finishes in ~0.01s instead of the full 41 seconds. That’s the one scenario where it’s not completely embarrassing.

The already-sorted column is the most interesting. Mergesort and quicksort don’t care much — they still do $O(n \log n)$ work. Timsort detects the entire array is one run and barely does anything.

What to Actually Say in an Interview

If someone asks “what’s the time complexity of quicksort?” and you say $O(n \log n)$ without qualification, you’ll get a follow-up: “what about worst case?” Know the answer: $O(n^2)$, triggered by poor pivot selection on sorted or nearly-sorted data.

For mergesort: always $O(n \log n)$, stable (preserves the relative order of equal elements), but needs $O(n)$ auxiliary space.

For practical Python questions, the answer is almost always “use sorted() or .sort()” because Timsort is genuinely excellent and the C implementation is hard to beat. If they ask why, talk about natural run detection and cache-friendly memory access patterns.

Where quicksort beats mergesort in practice: in-place sorting of large arrays where memory allocation is expensive. Quicksort’s average-case constant factor is smaller, and it doesn’t create intermediate arrays. For random data in C, quicksort often wins. In Python, neither comes close to Timsort because the overhead is dominated by interpreter costs, not algorithmic work.

The CPython sort implementation is worth reading if you want to understand what Timsort actually does at the code level — it’s well-commented and the original design doc is linked in the source.

One thing I haven’t tested at scale: the behavior when the comparison function itself is expensive. For sorting objects with a complex __lt__, the number of comparisons matters a lot more than memory allocations. Mergesort does ~$n \log n$ comparisons and quicksort does roughly the same on average, but with different constant factors. My best guess is that quicksort’s smaller number of comparisons in practice would show up more noticeably with expensive comparators — but I haven’t profiled this.

Space Complexity Worth Remembering

Bubble sort: $O(1)$ extra space, in-place swaps.

Quicksort: $O(\log n)$ average stack depth for recursion, $O(n)$ worst case on a degenerate partition.

Mergesort: $O(n)$ for the merge buffer. This is the reason some memory-constrained environments (embedded systems, certain database internals) avoid it.

Timsort: $O(n)$ in the worst case. In practice the merge buffer is sized to the smaller of the two runs being merged, so on nearly-sorted data with many small runs the working memory is much less than $n$.

The space question matters in interviews more than people realize — especially if you’re sorting linked lists (where mergesort is actually preferred over quicksort because you can merge without random-access indexing, avoiding the memory penalty).

FAQ

Q: When should I implement sorting from scratch instead of using Python’s built-in?
Almost never in production. The built-in sorted() and .sort() are implemented in C and use Timsort, which is faster than anything you’ll write in pure Python. Implement from scratch only in coding interviews where they explicitly ask you to, or when you need a custom sorting network for specific hardware constraints.

Q: Is quicksort always faster than mergesort in Python?
For random data, yes — quicksort’s in-place operation avoids the allocation overhead. But on nearly-sorted or partially-sorted data, the difference shrinks. And both are crushed by Timsort. If you’re choosing between the two for an interview answer, pick mergesort when stability matters (sorting objects by one key that already have another key sorted), and quicksort for raw speed on random data.

Q: Why does my quicksort hit RecursionError on sorted input?
Without a good pivot strategy, quicksort on sorted input degenerates to $O(n^2)$ with recursion depth equal to $n$. Python’s default recursion limit is 1000. Fix it by using median-of-three pivot selection, random pivot selection, or switching to an iterative implementation. In interviews, always mention this edge case when you write a quicksort — it shows you know the algorithm’s weak points.

Bottom line: use sorted() for everything real. Implement mergesort when stability is required and you’re asked to implement something. Implement quicksort when they explicitly want in-place $O(n \log n)$ and always use median-of-three pivot. Never implement bubble sort outside of a pedagogical demo.

What I’m still curious about: how Timsort’s galloping mode actually performs on adversarial inputs designed to maximize merge work. There’s a whole literature on Timsort correctness that I’ve only skimmed — the “Timsort is not optimal” paper by de Gouw et al. found a correctness bug in Java’s Timsort implementation (not mergesort — Java switched to Timsort for object sorting in Java 7) using formal verification, which is a fascinating rabbit hole if you have time.