Merge sort vs quicksort: which one to write in an interview and why

Short answer. Merge sort splits the array in half, sorts each half and merges. Quicksort picks a pivot and moves smaller values left, larger right. Then it sorts both sides. Both run in O(n log n) on average. Merge sort is stable and predictable; quicksort is faster in place. Interviewers ask you to write one and explain the other.

How does merge sort work?

Split the array into two halves. Sort each half the same way. Then merge two sorted halves in one pass with two indexes.

The recursion depth is log n. Each level does O(n) work in the merge. That gives O(n log n) in every case, best and worst.

The cost is memory. Merging needs a second array of size n.

How does quicksort work?

Pick a pivot value. Partition the array: smaller values go left of the pivot, larger go right. The pivot is now in its final place. Sort the two sides.

Partition happens in place, so extra memory is only the recursion stack. With a random pivot the expected time is O(n log n).

A bad pivot on every level gives O(n²). Sorted input with the first element as pivot does exactly that.

Merge sort vs quicksort: which one should you pick?

Property	Merge sort	Quicksort
Worst case	O(n log n)	O(n²), rare with a random pivot
Extra memory	O(n)	O(log n) stack
Stable	Yes	No
Linked lists	Natural fit	Awkward
Cache behaviour	Good	Better, in place
Used by	Python sorted (Timsort), Java objects	C qsort, Java primitives

Pick merge sort when stability matters. Pick it for linked lists too. Pick quicksort when memory is tight and average speed matters.

When does a problem need merge sort specifically?

• "Count inversions" or "count smaller numbers after self". The merge step counts them for free.
• "Sort a linked list in O(n log n)". Merge sort needs no random access.
• "External sort" of data that does not fit in memory.
• Any sort where equal keys must keep their input order.

What does one merge step look like?

Take the halves [2, 5, 9] and [1, 6]. Two indexes start at 0. Compare 2 and 1: take 1. Compare 2 and 6: take 2. Compare 5 and 6: take 5. Compare 9 and 6: take 6.

The right half is empty now. Append the rest of the left half: 9. Result: [1, 2, 5, 6, 9]. Five comparisons at most, one for each element placed.

Quicksort's partition on [5, 3, 8, 1, 9] with pivot 5 works differently. Walk from the left until a value at or above 5, walk from the right until a value at or below 5, swap. The result is [1, 3] on one side and [8, 9] on the other. The pivot sits between them.

How do you write merge sort and quicksort in Python?

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:       # <= keeps it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

import random

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    pivot = a[random.randint(lo, hi)]
    i, j = lo, hi
    while i <= j:
        while a[i] < pivot: i += 1
        while a[j] > pivot: j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i += 1; j -= 1
    quick_sort(a, lo, j)
    quick_sort(a, i, hi)

The quicksort above uses Hoare style partition with a random pivot. It handles duplicates without going quadratic.

How does merge sort solve Count of Smaller Numbers After Self?

For each element, count how many elements to its right are smaller. The naive loop is O(n²).

Run merge sort on pairs (value, original index). Now watch the merge. You take an element from the left half. Every element already taken from the right half is smaller. Add that count to the left element's answer.

The counting rides on the merge. The total stays O(n log n). This is the most common "hard" question built on merge sort.

What mistakes break these sorts in an interview?

• Using < instead of <= in the merge. The sort stops being stable.
• Taking the first element as the quicksort pivot. Sorted input turns quadratic.
• Recursing on [lo, hi] instead of [lo, j] and [i, hi]. That loops forever.
• Copying slices at every level in Python. Fine for an interview, slow at scale.

How do you explain merge sort against quicksort in an interview?

Start with the shared shape: divide and conquer, depth log n. Then name the one difference. Merge sort does the work after the split, quicksort does it before.

Give the trade. Merge sort: stable, O(n) memory. Quicksort: in place, O(n²) worst case. Mention that Python's sorted is a merge sort variant. That shows you know what runs in production.

Practise telling these two apart on the fast sort page. The whole map of patterns lives in LeetCode patterns.

FAQ

Is quicksort always faster than merge sort?

On arrays of primitives in memory, usually yes, by a constant factor. On linked lists or when stability is required, merge sort wins.

What is Timsort?

A merge sort that first finds runs already in order. Then it merges them. Python and Java use it for objects. Sorted or nearly sorted input runs in O(n).

Do I need to write these from memory?

Merge sort yes, in about 15 lines. For quicksort, interviewers mostly want the partition step and the pivot discussion.