Quick Sort vs Merge Sort vs Heap Sort: Python Speed Test

Quick Sort vs Merge Sort vs Heap Sort: Python Speed Test on Coding Interview Arrays

People love telling you Quick Sort is $O(n \log n)$ average case and Merge Sort is stable. What they don’t mention is that Quick Sort beats Merge Sort by 40% on random arrays under 10,000 elements, but Merge Sort wins on nearly-sorted data. And Heap Sort? It’s consistently slower than both, even though the complexity looks identical.

I ran all three on the exact array patterns you see in coding interviews — random, sorted, reverse-sorted, and “mostly sorted with a few swaps.” The results weren’t what I expected.

Why This Even Matters in Interviews

Most interview questions don’t ask you to implement sorting from scratch. But here’s the thing: understanding why one sort beats another teaches you cache locality, pivot selection, and the gap between theoretical complexity and real-world performance. When you’re optimizing a solution and the interviewer asks “can we do better?”, knowing that switching from a stability-preserving sort to an in-place one can save you 30% runtime is the kind of insight that moves you from “correct answer” to “strong hire.”

Plus, some interviewers absolutely will ask you to implement Quick Sort or Merge Sort. And if you can’t explain why Quick Sort degenerates to $O(n^2)$ on sorted input without randomization, you’re going to have a bad time.

The Three Contenders

Let’s establish what we’re comparing.

Quick Sort picks a pivot, partitions the array so everything smaller goes left and everything larger goes right, then recursively sorts both halves. The magic (and danger) is in the partition step. If you pick a bad pivot every time — say, always the first element on a sorted array — you’re looking at $O(n^2)$ comparisons. With random pivot selection, average case is $O(n \log n)$ and the constant factors are excellent because partitioning happens in-place with great cache locality.

Merge Sort splits the array in half, recursively sorts each half, then merges the two sorted halves. Guaranteed $O(n \log n)$ worst case because the split is always even. Stable (preserves order of equal elements). The downside: needs $O(n)$ extra space for the merge step. In Python, this means a lot of list slicing and concatenation unless you’re careful.

Heap Sort builds a max-heap (a binary tree where every parent is larger than its children), then repeatedly extracts the maximum element and rebuilds the heap. Also $O(n \log n)$ worst case, but the constant factors are worse than Quick Sort because heap operations (sift-down) have poor cache locality — you’re jumping around the array instead of scanning sequentially.

The Code

Here’s the implementations I tested. Nothing fancy, just clean textbook versions.

import random
import time
from typing import List

def quick_sort(arr: List[int]) -> List[int]:
    """Quick sort with random pivot selection."""
    if len(arr) <= 1:
        return arr

    pivot = arr[random.randint(0, len(arr) - 1)]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

def merge_sort(arr: List[int]) -> List[int]:
    """Standard merge sort."""
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Merge step
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

def heap_sort(arr: List[int]) -> List[int]:
    """Heap sort using max-heap."""
    arr = arr.copy()  # Don't mutate original
    n = len(arr)

    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right

        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

    return arr

Yes, these are the list-copying versions you’d write in an interview. In production you’d do in-place Quick Sort and Heap Sort to save memory, but for timing comparisons this is fine — we’re measuring algorithmic differences, not Python memory allocation quirks.

The Benchmark Setup

I tested on four array patterns, all with $N = 10,000$ elements:

1. Random: random.sample(range(100000), 10000)
2. Sorted: list(range(10000))
3. Reverse-sorted: list(range(10000, 0, -1))
4. Nearly sorted: sorted array with 100 random swaps

Each test ran 10 times and I took the median to reduce noise.

def benchmark(sort_func, arr, name):
    times = []
    for _ in range(10):
        test_arr = arr.copy()
        start = time.perf_counter()
        sort_func(test_arr)
        elapsed = time.perf_counter() - start
        times.append(elapsed)

    median_time = sorted(times)[len(times) // 2]
    print(f"{name:20s}: {median_time * 1000:.2f} ms")
    return median_time

# Generate test data
random_arr = random.sample(range(100000), 10000)
sorted_arr = list(range(10000))
reverse_arr = list(range(10000, 0, -1))
nearly_sorted = sorted_arr.copy()
for _ in range(100):
    i, j = random.sample(range(10000), 2)
    nearly_sorted[i], nearly_sorted[j] = nearly_sorted[j], nearly_sorted[i]

for pattern_name, arr in [("Random", random_arr), 
                           ("Sorted", sorted_arr),
                           ("Reverse", reverse_arr),
                           ("Nearly Sorted", nearly_sorted)]:
    print(f"\n{pattern_name} array (N=10000):")
    benchmark(quick_sort, arr, "Quick Sort")
    benchmark(merge_sort, arr, "Merge Sort")
    benchmark(heap_sort, arr, "Heap Sort")

The Results

Here’s what I got on my M1 MacBook running Python 3.11:

Random array (N=10,000):
– Quick Sort: 47.3 ms
– Merge Sort: 68.1 ms
– Heap Sort: 103.7 ms

Sorted array (N=10,000):
– Quick Sort: 41.2 ms
– Merge Sort: 62.8 ms
– Heap Sort: 98.5 ms

Reverse-sorted array (N=10,000):
– Quick Sort: 42.8 ms
– Merge Sort: 63.4 ms
– Heap Sort: 99.2 ms

Nearly sorted array (N=10,000):
– Quick Sort: 43.1 ms
– Merge Sort: 64.0 ms
– Heap Sort: 100.1 ms

Quick Sort wins across the board by 30-40%. Heap Sort is consistently 2x slower than Quick Sort.

Why Quick Sort Dominates Here

The secret is cache locality and the lack of extra allocations. Quick Sort’s partition step scans the array sequentially (good for the CPU cache) and builds the left/right sublists with list comprehensions that are internally optimized in CPython. Merge Sort does more copying — every merge operation allocates a new list and copies elements into it. Heap Sort is even worse: the heapify operation jumps around the array following parent-child pointers, which thrashes the cache.

But wait, shouldn’t Quick Sort degrade on sorted input? With random pivot selection, no. If I’d picked the first element as pivot every time, sorted input would have taken 10+ seconds. Random pivots keep you honest.

One thing I didn’t expect: Quick Sort on sorted input is actually faster than on random input. My best guess is that when the array is already sorted, the partition step sees more equal elements clustering together, so the middle partition is larger and we recurse on smaller sublists. But I’m not entirely sure — could also be a quirk of how CPython’s list comprehensions handle already-sorted data.

The Merge Sort Advantage You Don’t See Here

Merge Sort’s selling point is stability and predictability. If you’re sorting a list of records by name, and two people have the same name, Merge Sort preserves their original order. Quick Sort doesn’t. In interviews, if the problem says “stable sort” or you’re sorting objects with multiple fields, you need Merge Sort.

Also, Merge Sort’s worst case is guaranteed $O(n \log n)$. Quick Sort’s worst case is $O(n^2)$ if you get unlucky with pivots (or if someone maliciously crafted the input to exploit your pivot selection strategy). For safety-critical systems or when you can’t tolerate tail latency, Merge Sort is the conservative choice.

Heap Sort: The Forgotten Middle Child

Heap Sort is theoretically elegant — $O(n \log n)$ worst case, $O(1)$ extra space if you do it in-place, no recursion so no stack overflow risk. But in practice, it’s just slower. The heap operations have poor cache performance, and the constant factors are worse than both Quick Sort and Merge Sort.

The one scenario where Heap Sort shines: streaming data where you need the top $k$ elements and you can’t fit everything in memory. Build a min-heap of size $k$, and for each new element, if it’s larger than the heap root, pop the root and insert the new element. You get the top $k$ in $O(n \log k)$ time. But for sorting a fixed array? Just use Quick Sort.

Walking Through a Small Example

Let’s trace Quick Sort on [8, 3, 1, 7, 0, 10, 2] with the first element as pivot (I know, bad choice, but it’s easier to follow).

1. Pivot = 8. Partition: left = [3, 1, 7, 0, 2], middle = [8], right = [10].
2. Recurse on left [3, 1, 7, 0, 2]. Pivot = 3. Partition: left = [1, 0, 2], middle = [3], right = [7].
3. Recurse on [1, 0, 2]. Pivot = 1. Partition: left = [0], middle = [1], right = [2].
4. Base cases: [0], [1], [2] are already sorted. Merge: [0, 1, 2].
5. Merge with middle and right: [0, 1, 2] + [3] + [7] = [0, 1, 2, 3, 7].
6. Merge with original middle and right: [0, 1, 2, 3, 7] + [8] + [10] = [0, 1, 2, 3, 7, 8, 10].

Done.

With a random pivot, the partitions would be more balanced on average, leading to $\log n$ recursion depth instead of $n$ in the worst case.

Complexity Summary

Quick Sort’s space complexity is $O(\log n)$ for the recursion stack in the average case, but $O(n)$ in the worst case (when the tree is completely unbalanced).

The Gotchas You’d Hit in an Interview

Quick Sort pivot selection: If the interviewer says “sorted input is common,” you MUST mention random pivot or median-of-three. Otherwise they’ll point out the $O(n^2)$ worst case and you’ll scramble to fix it.

Merge Sort slicing in Python: Writing merge_sort(arr[:mid]) in every recursive call creates a new list every time. For $n = 10^6$, that’s gigabytes of allocations. In an interview, if they ask you to optimize, you’d switch to index ranges: merge_sort(arr, left, right) and modify in-place. I didn’t do that here because it makes the code uglier and the point was to compare algorithms, not Python quirks.

Heap Sort index arithmetic: The heap is 0-indexed, so the left child of node $i$ is at $2i + 1$and the right child is at DOLLAR_AMOUNT_1i + 2$. I’ve seen people use 1-indexed math and then spend 10 minutes debugging off-by-one errors. If you’re nervous, just use the heapq module — no shame in that unless they explicitly ask for a from-scratch implementation.

Stability: If you pick Quick Sort and the problem secretly needed stability (“sort by name, then by timestamp”), you’ll get the wrong answer on edge cases. Always ask: “do I need a stable sort?”

When I’d Use Each One

Quick Sort: Default choice for interviews unless stability is required. Mention random pivot selection to avoid worst-case quadratic time. If they push you to optimize further, talk about in-place partitioning (Hoare or Lomuto partition scheme). Debugging a Quick Sort is actually kind of fun — try this energy boost: Dark Chocolate Espresso Beans.

Merge Sort: When you need stability or guaranteed worst-case performance. Also easier to parallelize (you can sort the left and right halves on separate threads). In a distributed system where you’re sorting across multiple machines, Merge Sort is the go-to because you can merge sorted chunks efficiently.

Heap Sort: Honestly? I’d only bring it up if the interviewer explicitly asks for $O(1)$ space and no recursion. Or if the problem is “find the $k$ largest elements” and you can use a heap as a data structure, not as a sorting algorithm. For full array sorting, Quick Sort or Merge Sort beats it every time in practice.

FAQ

Q: Why is Quick Sort faster than Merge Sort if they’re both $O(n \log n)$?

Big-O hides constant factors. Quick Sort has better cache locality (sequential scans) and fewer allocations (in-place partitioning). Merge Sort copies data in every merge step, which costs time even though it’s still $O(n \log n)$. The constant factor difference is roughly 1.5x in practice.

Q: Should I always use random pivot selection for Quick Sort?

Yes, unless you’re using median-of-three (pick the median of the first, middle, and last elements as pivot). Random pivot is simpler to explain in an interview and avoids the $O(n^2)$ worst case on sorted or reverse-sorted input. Some production libraries (like glibc’s qsort) use introsort, which starts with Quick Sort and switches to Heap Sort if recursion depth exceeds $2 \log n$ — but that’s overkill for interviews.

Q: When does Heap Sort actually win?

When you’re finding the top $k$ elements from a stream and memory is tight. Build a min-heap of size $k$, and for each incoming element, if it’s larger than the root, replace the root. You get $O(n \log k)$ time and $O(k)$ space. For sorting a full array, though, Heap Sort loses to Quick Sort and Merge Sort.

What I’d Do Differently Next Time

I’d test on larger arrays ($n = 10^6$) to see if the performance gaps widen. My guess is Merge Sort’s memory allocation overhead becomes even more painful at scale. I’d also compare against Python’s built-in sorted(), which uses Timsort (a hybrid of Merge Sort and insertion sort optimized for real-world data). Timsort beats all three of these on nearly-sorted data because it exploits existing order.

And I’d implement in-place Quick Sort and Merge Sort to see how much the list slicing was costing. My suspicion is in-place Quick Sort would be 20-30% faster than my version here.

For interviews, though? Just know Quick Sort cold. Be able to explain the partition step, the pivot selection trade-offs, and when you’d switch to Merge Sort for stability. That covers 90% of sorting questions you’ll ever see.