Algorithms · intermediate
Merge sort vs quicksort
Merge sort recursively sorts halves and merges them with predictable Theta(n log n) time, while quicksort partitions around pivots and is typically fast in place but can degrade to Theta(n^2) with poor partitions.
Why it matters
The comparison exposes how stability, auxiliary memory, pivot strategy, worst-case guarantees, and data layout affect a sorting choice beyond a single complexity label.
Mental model
How to reason about merge sort vs quicksort
Merge sort pays for an orderly merge after balanced splits. Quicksort pays for partitioning and relies on pivots to keep the recursive subproblems balanced.
Analogy
Merge sort splits a deck into piles and carefully merges sorted piles. Quicksort chooses a divider, sends smaller and larger cards to opposite sides, then repeats within each side.
Examples
See the boundary, not just the happy path
Worked example · Stable record sorting
sort employees by department while preserving prior name orderA stable merge sort preserves the earlier relative order of equal department keys, which can be an explicit requirement.
Worked example · Balanced quicksort partition
partition n values into roughly n/2 and n/2Logarithmic recursion depth times linear partition work per level yields Theta(n log n) time for these balanced partitions.
Useful contrast · Hostile pivot sequence
always choose the smallest value as pivotPartitions of sizes 0 and n-1 produce linear recursion depth and Theta(n^2) comparisons unless pivot selection is improved.
Common mistakes
Misconceptions to remove early
Calling quicksort unconditionally O(n log n)
That is its expected or average behavior under suitable pivot assumptions. Its basic worst case is Theta(n^2).
Assuming merge sort is always in place
Array merge sort usually needs Theta(n) auxiliary storage. Linked-list and specialized variants have different storage trade-offs.
Quick check
Can you predict the result?
1. Which algorithm has a straightforward worst-case Theta(n log n) comparison bound?
- • Merge sort
- • Basic quicksort with arbitrary pivots
- • Bubble sort
2. Why can quicksort still perform well in practice?
Keep building