Sorting as a Tool
Intermediate · 16 min read · Problem-Solving Patterns, Searching & Sorting
Custom comparators, counting sort and quickselect for the k-th element.
You'll rarely be asked to implement a sorting algorithm in an interview — but you'll constantly use sorting as a tool. Sorting first is often the step that turns a messy problem into a simple pass: duplicates become neighbours, overlaps become adjacent, pairs become findable with two pointers.
Sort first: the cheapest trick in the book
Sorting costs O(n log n), and that's below most problems' budget (see the constraints table in Big-O). After sorting:
Custom comparators
A comparator returns negative if a should come first, positive if b should, zero if tied. Build multi-key orders with Comparator helpers:
Counting and bucket sort: O(n) when values are small
Comparison sorts can't beat O(n log n). But if values lie in a small range [0, k], you don't need comparisons — just count:
Quickselect: the k-th element without sorting
To find the k-th largest, you don't need the full order — just the element that would land at index n − k. Partition around a pivot (as in quicksort), and the pivot ends up at its final sorted position. Then continue into only one side.
Which tool when?
Practice ladder
Interview questions
- What is the time complexity of quickselect, and how do you avoid the worst case?
- Why can counting sort beat O(n log n)?
Further reading
Key takeaways
- Sorting first is often the step that makes a problem easy — but it loses indexes, so sort indexes or pairs when needed.
- Comparators can be the solution (largest number); use Integer.compare, never subtraction.
- Small value ranges → counting or bucket sort in O(n).
- k-th element → quickselect, O(n) average with a random pivot; top k streaming → a heap.