How it works
Merge sort always splits evenly and always costs n log n, but needs linear extra space. Quick sort partitions in place and is usually faster, but degrades to quadratic on a bad pivot.
Choose merge sort when worst-case guarantees matter and quick sort when average performance and memory do.
Common error
Claiming quick sort is always faster. On sorted input with a naive pivot it is the slowest of the two by a wide margin.
Worked example
Example
Merge sorted runs [1, 4] and [2, 3]
Choose smallest front: 1, then 2, then 3
Append remaining 4
Result: [1, 2, 3, 4]Merge sort divides input and merges sorted results, giving O(n log n) time in its standard form and requiring auxiliary storage. Quicksort partitions around a pivot; balanced partitions are efficient, but repeatedly extreme pivots can produce quadratic time.
Exercises
2.3.1 · Explain
What is the merge result for sorted runs [2, 5] and [1, 3, 6]?
Show solution
The result is [1, 2, 3, 5, 6]. Repeatedly take the smaller available front item, then append any remaining run.
2.3.2 · Explain
Why can already sorted input be a bad case for quicksort that always uses an endpoint pivot?
Show solution
Distinct sorted input can yield a partition of size zero and another of size n - 1 repeatedly. The resulting work sums to quadratic time.