Merge Sort and Quicksort in Python, Timed Against Each Other

Fri Aug 14 2026

Merge sort splits the input in half, sorts each half recursively, and merges the two sorted halves back together. Quicksort picks a pivot, partitions the input around it, and recurses on the two partitions. This post runs both on a small list to check correctness, then times both on the same 5000 random integers.

The code

import random
import time


def merge_sort(arr):
    # Split in half, sort each half recursively, then merge two sorted
    # halves into one sorted list.
    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]:
            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):
    # Pick a pivot, partition into less-than/equal/greater-than, recurse
    # on the two unequal partitions.
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quicksort(less) + equal + quicksort(greater)


small = [38, 27, 43, 3, 9, 82, 10]
print("input:", small)
print("merge_sort:", merge_sort(small))
print("quicksort: ", quicksort(small))

random.seed(42)
big = [random.randint(0, 1_000_000) for _ in range(5000)]

start = time.perf_counter()
merge_result = merge_sort(big)
merge_time = time.perf_counter() - start

start = time.perf_counter()
quick_result = quicksort(big)
quick_time = time.perf_counter() - start

print(f"\ntiming on {len(big)} random ints (seed=42):")
print(f"merge_sort: {merge_time:.6f}s")
print(f"quicksort:  {quick_time:.6f}s")
print("both produced the same sorted result:", merge_result == quick_result)
print("matches Python's sorted():", merge_result == sorted(big))

Both functions run against the same 7-element list first, then against the same 5000-element list of random integers (random.seed(42) fixes the sequence so the input is reproducible). The script also checks merge_result == quick_result and compares both against Python’s built-in sorted().

Running it

Real output:

input: [38, 27, 43, 3, 9, 82, 10]
merge_sort: [3, 9, 10, 27, 38, 43, 82]
quicksort:  [3, 9, 10, 27, 38, 43, 82]

timing on 5000 random ints (seed=42):
merge_sort: 0.005712s
quicksort:  0.004581s
both produced the same sorted result: True
matches Python's sorted(): True

On the small list, both functions produced the identical sorted result [3, 9, 10, 27, 38, 43, 82]. On 5000 random integers, merge_sort took 0.005712s and quicksort took 0.004581s in this run, and both checks passed: merge_result == quick_result and merge_result == sorted(big) both printed True.

Takeaway

Both implementations agreed with each other and with Python’s own sorted() on 5000 random integers, and in this run quicksort measured faster than merge sort on that input — 0.004581s versus 0.005712s.