Skip to interview prep
Apexed

349. Compare merge sort and quicksort using their divide-and-conquer recurrences.

MediumDivide & conquer

Technical
Show model answer

Merge sort always splits evenly and merges in linear time: T(n) = 2T(n/2) + Θ(n) = Θ(n log n) in every case. It needs O(n) auxiliary space for arrays, is stable, and suits linked lists and external sorting. Quicksort partitions around a pivot: T(n) = T(k) + T(n − k − 1) + Θ(n). Balanced splits give Θ(n log n), but always choosing the minimum or maximum (sorted input with a first-element pivot) gives T(n) = T(n − 1) + n = Θ(n²).

With a random pivot the expected number of comparisons is about 2n ln n ≈ 1.39 n log₂ n. Quicksort is in-place, cache friendly and usually faster in practice, but not stable. Recursing on the smaller side first and looping on the larger keeps the stack at O(log n); introsort falls back to heapsort to cap the worst case at O(n log n).

Compare merge sort and quicksort using their divide-and-conquer recurrences. — Data structures & algorithms interview question — Apexed