Merge Sort vs Quick Sort: Cache & Pivot Benchmark Results

Why Quick Sort Sometimes Loses to Merge Sort

Quick sort is faster than merge sort in most textbooks. But run them on a million integers and sometimes merge sort wins by 15-20%. The reason isn't algorithmic complexity—it's cache misses and pivot strategy.

I benchmarked both algorithms with different pivot selection methods (first element, random, median-of-three) and array sizes from 1K to 10M elements. The results show that quick sort's performance collapses when you pick bad pivots, and merge sort's sequential memory access pattern gives it an edge on modern CPUs with multi-level caches.

This post walks through the implementations, shows you the exact benchmark numbers, and explains when each algorithm actually wins in practice.

The Core Implementations

Here's merge sort. It splits the array recursively, then merges sorted halves:

python
import random
import time
from typing import List

def merge_sort(arr: List[int]) -> List[int]:
    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: List[int], right: List[int]) -> List[int]:
    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:])

---

*Continue reading the full article on [TildAlice](https://tildalice.io/merge-sort-vs-quick-sort-cache-pivot-benchmark/)*