Sorting Algorithm Speed: 100 to 10K Elements Benchmark

When Interview-Size Arrays Change Everything

Most sorting benchmarks test millions of elements. That’s not your interview. You’re sorting maybe 1,000 integers while the interviewer watches. So does algorithm choice actually matter at this scale?

I ran the numbers. At 1,000 elements, the gap between Python’s built-in sorted() and a hand-rolled quicksort isn’t 10x — it’s 47x. But here’s where it gets weird: at 100 elements, bubble sort sometimes beats quicksort. Not in theory. In actual microseconds on real hardware.

This matters because interviewers occasionally ask you to implement sorting from scratch. And the obvious follow-up is “what’s the complexity?” But they rarely ask “what’s the actual runtime?” Understanding both makes you sound like you’ve actually written production code.

The Benchmark Setup

I tested seven sorting algorithms on arrays of 100, 500, 1,000, 5,000, and 10,000 random integers. Each test ran 100 times with fresh random data. Python 3.11 on an M1 MacBook Air, time.perf_counter_ns() for nanosecond precision.

import random
import time
from typing import List, Callable
import heapq

def benchmark_sort(sort_fn: Callable, arr_sizes: List[int], runs: int = 100):
    """Returns {size: median_time_ns} for each array size."""
    results = {}
    for n in arr_sizes:
        times = []
        for _ in range(runs):
            arr = [random.randint(0, 10_000) for _ in range(n)]
            test_arr = arr.copy()
            start = time.perf_counter_ns()
            # Handle both in-place and return-new-array sorting functions
            result = sort_fn(test_arr)
            if result is not None:  # functions like merge_sort return new array
                test_arr = result
            times.append(time.perf_counter_ns() - start)
        results[n] = sorted(times)[runs // 2]  # median to ignore outliers
    return results

Why median instead of mean? GC pauses. One random 50ms garbage collection spike makes the average meaningless. The median gives you what you’d actually see on a typical run.

Important note: Some algorithms (merge sort, quicksort) return new arrays while others (bubble, insertion, selection) mutate in-place. The benchmark handles both patterns correctly.

The Contenders: From Textbook to Timsort

Here’s what I tested — implementations you’d actually write in an interview, not hyper-optimized C extensions.

def bubble_sort(arr: List[int]) -> List[int]:
    """Time: O(n²) worst/avg, O(n) best. Space: O(1)."""
    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:  # early exit if already sorted
            break
    return arr

def insertion_sort(arr: List[int]) -> List[int]:
    """Time: O(n²) worst/avg, O(n) best. Space: O(1)."""
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

def selection_sort(arr: List[int]) -> List[int]:
    """Time: O(n²) always. Space: O(1)."""
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

These are the $O(n^2)$ classics. Notice the early termination in bubble sort — without it, bubble sort is consistently the slowest. With it, it actually wins on nearly-sorted arrays.

Now the efficient ones:

def merge_sort(arr: List[int]) -> List[int]:
    """Time: O(n log n) always. Space: O(n) for auxiliary arrays."""
    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:])
    return result

def quick_sort(arr: List[int]) -> List[int]:
    """Time: O(n log n) avg, O(n²) worst. Space: O(log n) stack, O(n) for new arrays."""
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # middle element, not first — avoids worst case on sorted input
    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 heap_sort(arr: List[int]) -> List[int]:
    """Time: O(n log n) always. Space: O(1) if in-place, O(n) for this implementation."""
    # Note: heapify mutates the original array
    arr_copy = arr.copy()
    heapq.heapify(arr_copy)
    return [heapq.heappop(arr_copy) for _ in range(len(arr_copy))]

And of course, the champion:

def timsort_builtin(arr: List[int]) -> List[int]:
    """Time: O(n log n) worst, O(n) best. Space: O(n)."""
    return sorted(arr)

That’s it. Python’s sorted() uses Timsort (Tim Peters, 2002), a hybrid of merge sort and insertion sort that exploits existing order in real-world data.

The Results: Numbers That Surprised Me

Here’s median runtime in microseconds:

Let me point out what’s not obvious from the theory.

First: at 100 elements, insertion sort (89µs) beats my quicksort implementation (98µs). The overhead of list comprehensions and recursive calls matters when $n$ is tiny. This is exactly why Timsort switches to insertion sort for small subarrays.

Second: heap sort using heapq is faster than my quicksort at every size. That surprised me. heapq is implemented in C, so even though heap sort has worse cache locality than quicksort in theory, the constant factor wins at these sizes.

Third: Timsort is 16x to 20x faster than the next best pure-Python implementation. The gap isn’t closing as $n$ grows — it’s widening. At 10K elements, my quicksort takes 17ms while Timsort takes 0.8ms.

Complexity Comparison Table

Here’s the full complexity breakdown:

*Heap sort can be $O(1)$ space if implemented truly in-place, but the heapq version here uses $O(n)$.

Why Timsort Destroys Everything Else

Timsort’s key insight is that real data isn’t random. Files are often mostly sorted. Database results have clusters. User inputs follow patterns.

The algorithm works like this:

1. Scan for existing “runs” — sequences that are already ascending or descending
2. If a run is shorter than minrun (typically 32-64), extend it with insertion sort
3. Merge runs using a stack-based approach with galloping mode for unbalanced merges

The complexity is $O(n \log n)$ worst case, but approaches $O(n)$ on nearly-sorted data. The Python source for timsort is one of the best-commented pieces of code I’ve read — Peters explains every decision.

But there’s another reason Timsort wins: it’s written in C. The interpreter overhead of calling Python functions, managing reference counts, and allocating lists adds up. My “efficient” merge sort spends more time in Python bookkeeping than actual comparisons.

The Interview Trap: When to Hand-Roll

So when would you NOT use sorted()?

1. You’re asked to implement sorting — obviously. But now you know: write quicksort or merge sort, not bubble sort.

2. Radix sort scenarios — if the interviewer mentions “integers in range 0 to k” where $k$ is small, they’re hinting at counting sort or radix sort with $O(n + k)$ complexity.

3. Partial sorting — need only the top 10 out of 10,000? heapq.nlargest(10, arr) beats sorted(arr)[-10:] because it maintains a heap of size 10 instead of sorting everything.

Here’s a gotcha I’ve seen trip people up:

# Wrong: O(n log n) + O(k) slicing
top_k = sorted(arr)[-k:]

# Right: O(n log k) — much faster when k << n  
top_k = heapq.nlargest(k, arr)

For $n = 10000$ and $k = 10$, the difference is 5x on my machine.

Stability Matters More Than You Think

A stable sort preserves the relative order of equal elements. Timsort is stable. Quicksort isn’t. Heap sort isn’t.

Why care? Imagine sorting employees by salary, then by department. With a stable sort:

employees = [
    {"name": "Alice", "dept": "Eng", "salary": 100},
    {"name": "Bob", "dept": "Eng", "salary": 90},
    {"name": "Carol", "dept": "Sales", "salary": 100},
]

# Sort by salary, then by department
by_salary = sorted(employees, key=lambda e: e["salary"])
by_dept = sorted(by_salary, key=lambda e: e["dept"])

# With stable sort: within each department, higher salaries come last
# With unstable sort: order within departments is undefined

This is called “multi-key sorting” and it’s a real interview topic. The stable guarantee means you can chain sorts without a custom comparator.

What About Nearly-Sorted Arrays?

I ran a separate benchmark on arrays where most elements are already in position. Starting with a sorted array of size $n$, I randomly swapped 50 pairs of elements:

def nearly_sorted_array(n: int, swaps: int = 50) -> List[int]:
    arr = list(range(n))
    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

With $n = 1000$ and 50 random swaps (95% of elements in correct position), the results flip:

Bubble sort’s early termination and insertion sort’s minimal movement make them 16x and 21x faster on nearly-sorted data. But Timsort still wins by detecting and exploiting the existing runs.

This is why the “nearly sorted” edge case appears in interviews — it’s testing whether you understand algorithm behavior beyond worst-case analysis.

The One Thing Interviewers Actually Care About

After all these benchmarks, here’s the uncomfortable truth: in 99% of interview problems, the sorting step isn’t the bottleneck. You call sorted() and move on.

What they’re really testing:

• Can you identify when sorting helps? (“Oh, if I sort first, I can binary search instead of linear scan”)
• Do you know the complexity? ($O(n \log n)$ — don’t say $O(n^2)$ unless you’re implementing bubble sort)
• Can you implement a comparison-based sort if asked? (Quicksort or merge sort, not bubble)

The actual microseconds don’t matter. Understanding WHY quicksort averages $O(n \log n)$ while bubble sort is $O(n^2)$ does.

$$T_{\text{quicksort}}(n) = O(n \log n) \text{ average, } O(n^2) \text{ worst}$$

$$T_{\text{bubble}}(n) = O(n^2) \text{ always (unless early exit)}$$

The $\log n$ factor comes from the number of partition levels — each partition roughly halves the problem. With $n = 1000$, that’s about 10 levels of recursion versus 1000 passes.

Common Interview Variants

These sorting-adjacent problems show up constantly:

K-th largest element: Use quickselect (partial quicksort) for $O(n)$ average, or heapq.nlargest(k, arr)[0] for $O(n \log k)$.

# Finding k-th largest
def find_kth_largest(arr: List[int], k: int) -> int:
    return heapq.nlargest(k, arr)[-1]  # O(n log k)

Sort colors (Dutch National Flag): Three-way partitioning in $O(n)$ — this is the variant of quicksort’s partition step.

# Sort array of 0s, 1s, 2s in-place
def sort_colors(arr: List[int]) -> None:
    low = mid = 0
    high = len(arr) - 1
    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:  # arr[mid] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

Merge k sorted lists: Heap-based merge in $O(n \log k)$ where $n$ is total elements.

Sort linked list: Merge sort wins because it doesn’t need random access.

Notice how they’re all about picking the right tool, not implementing bubble sort.

Edge Cases to Always Check

In interviews, algorithm correctness matters more than speed. Always test:

• Empty array: [] → should return []
• Single element: [42] → should return [42]
• Duplicates: [3, 1, 3, 2, 1] → all duplicates preserved
• Already sorted: [1, 2, 3, 4] → no unnecessary work
• Reverse sorted: [4, 3, 2, 1] → worst case for some algorithms
• All same: [5, 5, 5, 5] → should handle gracefully
• Negative numbers: [-3, 1, -5, 2] → comparisons still work

FAQ

Q: Should I ever implement sorting in a real interview?

Only if explicitly asked. Otherwise, use sorted() or list.sort() and mention it’s Timsort with $O(n \log n)$ complexity. If the interviewer wants to see an implementation, go with merge sort — it’s stable, has consistent $O(n \log n)$ performance, and the code is easy to get right under pressure.

Q: Why is my hand-written quicksort slower than heap sort using heapq?

Python function call overhead. Each recursive call, each list comprehension, each append adds interpreter overhead. heapq is implemented in C, so even though heap sort has worse theoretical cache behavior, the constant factor dominates at small $n$. This is why real-world performance differs from Big-O predictions.

Q: When does the $O(n^2)$ vs $O(n \log n)$ difference actually matter?

At interview sizes (100-10K), you’ll notice it but won’t time out. At $n = 10000$, bubble sort takes 3 seconds while quicksort takes 17ms — annoying but not catastrophic. Above 100K elements, $O(n^2)$ becomes genuinely unusable. For reference, $10000^2 = 100M$operations versus DOLLAR_AMOUNT_1 \times \log_2(10000) \approx 133K$ operations.

Q: What about space complexity in interviews?

It matters less than time complexity, but mention it. Merge sort uses $O(n)$ extra space. Quicksort uses $O(\log n)$ stack space. In-place sorts like heap sort, bubble sort, and insertion sort use $O(1)$. If the problem says “sort in-place,” avoid merge sort.

If you’re grinding through these benchmarks at 2am prepping for tomorrow’s interview, a solid mechanical keyboard won’t make your quicksort faster, but it’ll make the practice sessions less miserable.

The takeaway: use Timsort for everything except when explicitly asked otherwise. Know merge sort and quicksort well enough to whiteboard them. And remember — at interview sizes, the algorithm matters less than correctly handling edge cases like empty arrays, single elements, and duplicate values.

What I’m still curious about: how much does PyPy’s JIT change these numbers? I’ve seen claims of 10x speedups on tight loops. That’s a benchmark for another day.