Sorting
A preprocessing step that unlocks two pointers, greedy and binary search.
What you actually need to hold in your head
- Comparison sorts bottom out at O(n log n)
- Counting and radix beat that on small key spaces
- Stability matters when sorting by multiple keys
- Custom comparators encode the greedy choice
Watch it run
Step through the algorithm before you write it.
Partition around a pivot, then recurse only into the side that contains the rank you want.
Walk the array swapping any pair that is out of order. After pass k the k largest values have bubbled to the end.
Repeatedly find the smallest remaining value and swap it into the next position. Always n squared comparisons, but at most n swaps.
Grow a sorted prefix by lifting each new element out and shifting bigger values right until it drops into place.
Split the array in half, sort each half recursively, then merge the two sorted runs in linear time.
Pick a pivot, partition everything smaller to its left and larger to its right, then recurse on both sides.
Tally how many times each key appears, turn the tally into positions with a prefix sum, then place elements from the back to stay stable.
Patterns in this topic
The trigger phrases are what you are training yourself to notice.
Split the input, solve the halves recursively, and do the real work while combining them.
Partition around a pivot and recurse only into the side that contains the target rank.
Sorting problems
Ordered by sheet phase, so the early ones are the highest signal.