Merge Sort vs Quick Sort: How to Choose, and Why

"They are both O(n log n)" is where most comparisons of these two stop, and it is the least interesting true thing you can say about them. The complexity is where they agree. Everything that decides which one a real system ships — memory, worst case, stability, cache behaviour — is where they do not.

The problem it solves

You need a sort, and the language already has one. So the real question in an interview is never "implement a sort"; it is "you have two O(n log n) options, which do you take and what does it cost you". Answering that needs one sentence about each algorithm's shape, not its pseudocode.

The intuition

The two algorithms do the same two things — divide and combine — in the opposite order.

Merge sort does the work on the way up. Splitting is free: cut the array in half, no thought required. All the intelligence is in the merge, where two sorted halves are zipped into one sorted whole.

Quick sort does the work on the way down. Partitioning is the whole algorithm: pick a pivot, move everything smaller to its left and everything larger to its right. Now the pivot is in its final position and the two sides never have to look at each other again. Combining is nothing — the pieces are already where they belong.

That single difference propagates into every practical property:

Merge sort's split is blind, so its shape is guaranteed. Quick sort's split is a guess, so its shape depends on the data.

Merge sort always produces two halves of size n/2, which means log n levels, always. Quick sort produces two sides of whatever size the pivot happened to imply. A median pivot gives the same clean halving; a pivot that is the minimum gives one empty side and one side of n-1, and the recursion turns into a loop that is O(n²).

Watch it run

Step through the split-and-merge tree. Notice that the descent does nothing but cut, and every bit of ordering happens as the pieces come back together.

Now picture the mirror image for quick sort: one pass over the array puts the pivot in its final home, and the tree below it is built from data that is already partly ordered.

The code

def merge_sort(nums, key=lambda x: x):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left, right = merge_sort(nums[:mid], key), merge_sort(nums[mid:], key)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if key(left[i]) <= key(right[j]):   # <= , not < : this is the stability
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]       # O(n) extra memory, at every level


def quick_sort(nums, key=lambda x: x, lo=0, hi=None):
    """Sorts in place. Lomuto partition, last element as pivot."""
    if hi is None:
        hi = len(nums) - 1
    while lo < hi:
        pivot, cut = key(nums[hi]), lo
        for k in range(lo, hi):
            if key(nums[k]) < pivot:
                nums[cut], nums[k] = nums[k], nums[cut]   # the swap that reorders equals
                cut += 1
        nums[cut], nums[hi] = nums[hi], nums[cut]
        if cut - lo < hi - cut:            # recurse into the smaller side only
            quick_sort(nums, key, lo, cut - 1)
            lo = cut + 1                   # ...and loop on the larger: O(log n) stack
        else:
            quick_sort(nums, key, cut + 1, hi)
            hi = cut - 1
    return nums


scores = [("ada", 2), ("bo", 1), ("cy", 2), ("di", 1)]
by_score = lambda person: person[1]

print([n for n, _ in merge_sort(scores, by_score)])      # ['bo', 'di', 'ada', 'cy']
print([n for n, _ in quick_sort(scores[:], by_score)])   # ['di', 'bo', 'ada', 'cy']

Both outputs are correctly sorted by score. Only one of them kept bo ahead of di, and bo came first in the input. That is stability, and it is not a detail you can add later — it is a consequence of <= in the merge and of the swap in the partition.

The complexity

Merge sort. O(n log n) time in the best, average and worst case — the split is blind, so no input can make it worse. O(n) extra space for the merge buffer. Stable.

Quick sort. O(n log n) average, O(n²) worst case when pivots are consistently extreme. O(log n) space for the recursion and nothing else; the partition works in place. Not stable.

The reason quick sort is nonetheless the faster of the two in practice is the part Big-O deliberately throws away. Partitioning reads and writes one contiguous block, so the data is in cache and the constant factor is small. Merge sort allocates a new array per level and copies into it; the memory traffic is real work that O(n log n) does not mention.

Where it goes wrong

• Calling quick sort's worst case theoretical. The classic pivot choice — first or last element — hits O(n²) on an already sorted array, which is the most common shape real data comes in. A random pivot or median-of-three makes the bad case improbable rather than predictable.
• Forgetting merge sort's memory on large inputs. O(n) extra is fine for a million ints and a problem when the array does not fit comfortably in memory. Externally — sorting files — that same property flips to an advantage, because merging streams sequentially is exactly what disks like.
• Claiming a sort is stable without checking. If the task is "sort by date, keep ties in their existing order", an unstable sort silently produces a plausible-looking wrong answer.
• Duplicates under Lomuto partitioning. An array of all-equal values sends every element to one side, so the partition is maximally lopsided and the sort degrades to O(n²). Three-way partitioning — smaller, equal, larger — fixes it.
• Reimplementing either one in production. Python's sorted is Timsort: merge sort adapted to exploit runs that are already ordered, stable, and O(n) on sorted input. Say that you know before you say you would write your own.

How to say it in an interview

Lead with the trade, not the mechanics:

"They are both O(n log n) on average, so I would choose on the guarantees. Merge sort is O(n log n) in every case and stable, but it needs O(n) extra space. Quick sort partitions in place, so it is O(log n) space and usually faster because of cache locality, but its worst case is O(n²) if the pivots are unlucky — which a random pivot makes rare. If I need a hard latency bound or stable ordering, merge sort. If memory is the constraint and average throughput is the goal, quick sort."

Then add the sentence most candidates leave out: "and if this is a real system, I would use the standard library's sort, which is a hybrid built on exactly this trade-off." Knowing when not to write the algorithm is part of knowing the algorithm.