You will rarely write a sorting algorithm from scratch in production — every language has a built-in sort. But you must understand how they work to answer "Why is this slow?" and "Which sort should I use here?" — both common interview questions.
Merge Sort (The Safe Bet)
Merge Sort uses Divide and Conquer: split the list in half recursively until every piece has exactly one element (a list of one element is always sorted). Then merge adjacent sorted pieces back together in order.
[38, 27, 43, 3]
→ [38, 27] and [43, 3]
→ [38] [27] [43] [3]
→ merge: [27, 38] and [3, 43]
→ merge: [3, 27, 38, 43]
| Property | Value |
|---|---|
| Time (all cases) | O(N log N) |
| Space | O(N) — needs a temporary array to merge into |
| Stable? | Yes — equal elements preserve their original order |
The O(N) space cost is Merge Sort's main drawback. For large datasets, allocating a second array of equal size is expensive.
Quick Sort (The Speed Demon)
Quick Sort picks a pivot element, then partitions the array: everything smaller than the pivot goes left, everything larger goes right. The pivot is now in its final sorted position. Repeat recursively on the left and right sub-arrays.
[38, 27, 43, 3, 9] pivot = 9
→ [3] [9] [38, 27, 43]
→ [3, 9] and recurse on [38, 27, 43] pivot = 43
→ [3, 9, 27, 38, 43]
| Property | Value |
|---|---|
| Time (average) | O(N log N) |
| Time (worst case) | O(N²) — when pivot selection is poor |
| Space | O(log N) — sorts in-place, only recursion stack |
| Stable? | No |
Quick Sort is typically faster in practice than Merge Sort despite the same average complexity. The reason is CPU cache locality: Quick Sort operates on contiguous memory in-place, which means the CPU cache stays warm. Merge Sort's copying to auxiliary arrays causes more cache misses.
What Does Python and Java Actually Use?
- Python's
sorted()uses Timsort — a hybrid of Merge Sort and Insertion Sort, designed for real-world data that is often partially sorted. It is stable and O(N log N). - Java's
Arrays.sort()for primitives uses a dual-pivot Quick Sort. For objects, it uses Timsort (to preserve stability). - C++
std::sortuses Introsort — Quick Sort that switches to Heap Sort if recursion depth exceeds O(log N), preventing the O(N²) worst case.