Quicksort intuition
Quicksort is the other famous divide-and-conquer sort, and the default in many languages' standard libraries. Instead of splitting by position (the middle), it splits by value:
- Pick a pivot value.
- Partition: everything smaller than the pivot goes left, everything bigger goes right.
- Quicksort each side.
After partitioning, the pivot is in its final sorted position and the two sides never interact again. On average the pivot lands near the middle, giving the same halving math as merge sort: O(n log n). But if the pivot is always the smallest or largest value, one side gets everything and it degrades to O(n²). That is the trade: usually faster in practice, with a bad worst case.
Code exercise · python
Run this. This readable version partitions with list comprehensions: smaller, equal, and bigger buckets around the pivot, then sorts the two outer buckets the same way.
Quiz
Which situation triggers quicksort's O(n²) worst case?
The sort-then-solve pattern
In interviews you will rarely implement a sort. You will call sorted() (Python's Timsort, O(n log n)) as step one of a bigger solution. Sorting buys you structure:
- Closest values become neighbors. Finding the minimum gap between any two numbers drops from O(n²) pair-checking to sort + one adjacent-pairs scan.
- Overlaps line up. Sort meetings by start time and conflicts can only be between neighbors.
- Binary search and two pointers unlock (lesson 2-2, and unit 4 coming up).
When a problem feels like it needs all-pairs comparisons, ask: would sorting make the answer local? Spending O(n log n) to avoid O(n²) is almost always a win.
Code exercise · python
Your turn. min_gap(nums) should return the smallest difference between ANY two numbers in the list. Sort first, then only compare neighbors.
Problem
You sort meetings by start time: (9, 10), (10, 11), (13, 15). Each pair is (start, end), and a meeting may start exactly when the previous one ends. Can one person attend all three? Answer yes or no.