Quicksort vs Mergesort

Both are O of n log n on average, so the interesting differences are not the asymptotics. Mergesort always hits that bound and always needs O of n extra space for its merge buffer. Quicksort sorts in place with only logarithmic stack space, but a bad pivot choice turns it into a quadratic algorithm, so its guarantee is expected rather than absolute.

The difference that bites hardest in production is stability. Mergesort is stable, so equal elements keep their relative order. Quicksort is not stable, and making it stable costs the in-place advantage. That matters whenever you sort records by one key while a second key implicitly breaks the tie, such as sorting events by timestamp while expecting a stable order of insertion.

There is also a constant factor difference that comes from memory rather than from counting comparisons. Mergesort copies elements into a second array, so every element is written twice. Quicksort swaps elements within one array, so it touches memory in place and benefits from the CPU cache, which in practice makes it faster than mergesort on random data despite the same asymptotic cost.

The trade-off to state in an interview is that neither dominates. Mergesort buys a worst case guarantee and stability with extra memory. Quicksort buys in-place operation and cache friendliness at the price of stability and a pathological input. Randomising the pivot removes the pathological case for all practical purposes, and Python's built-in sort sidesteps the choice entirely by using a stable, adaptive merge sort that also exploits existing runs in the data.

Sort records by one key only. A merge that takes the left element when the keys are equal keeps the original relative order, so the result is stable. A quicksort that partitions with the pivot first and swaps elements around it can move equal elements past each other, which destroys that order.

def merge_sort(items, key):
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    left = merge_sort(items[:mid], key)
    right = merge_sort(items[mid:], key)
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if key(left[i]) <= key(right[j]):
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]


def quicksort(items, key):
    if len(items) <= 1:
        return list(items)
    pivot = items[0]
    rest = items[1:]
    smaller = [x for x in rest if key(x) <= key(pivot)]
    larger = [x for x in rest if key(x) > key(pivot)]
    return quicksort(smaller, key) + [pivot] + quicksort(larger, key)


records = [("a", 1), ("b", 1), ("c", 0)]
print(merge_sort(records, lambda item: item[1]))
print(quicksort(records, lambda item: item[1]))

The merge sort output is c zero, then a one, then b one. The two records with key one keep the order they arrived in. The quicksort output is c zero, then b one, then a one: the two equal keys have swapped, because the pivot was taken from the front and the partition rebuilt the list in a different order.

The mechanism is the comparison in the merge. Using less than or equal means that when the keys are equal the left element, which came from the earlier part of the input, is taken first. The partition in quicksort has no such tie-break: the equal elements are collected into the same bucket but the pivot itself is placed between them, so the relative order of the equals is decided by the partition rather than preserved.

The trade-off to name is that you can make quicksort stable, but only by giving up the in-place property and paying the extra memory that makes mergesort stable. If you need stability, use mergesort or the built-in sort, both of which are stable in Python. If you do not, quicksort's cache behaviour usually makes it the faster choice on random data.