Sorting Algorithms You Actually Need for Coding Interviews
You rarely have to implement a sort from scratch in an interview, but you do need to know the trade-offs and recognize when sorting makes a problem easier.
The ones worth knowing
- Merge sort: O(n log n) every time, stable, needs O(n) extra space. Its merge step shows up in counting inversions and merging k lists.
- Quicksort: O(n log n) on average, in place, O(n^2) in the worst case. Its partition step powers quickselect.
- Heap sort: O(n log n), in place, not stable. Mostly useful for understanding heaps.
- Counting sort and bucket sort: O(n + k) when values fall in a small range, as in sorting colors or top-k frequent elements.
- Built-in sort: Timsort in Python and Java (for objects), stable, O(n log n). Say this when you use it.
When sorting first helps
- Two-sum style problems without extra memory: sort, then use two pointers.
- Interval problems: sort by start or end time.
- Grouping anagrams: sort each word to make a key.
- Greedy assignment: sort both arrays and match them.
What interviewers ask
- "Is your sort stable, and does it matter here?"
- "Can you do better than O(n log n)?" The answer is yes only when you know something about the value range.
- "What's the space cost?"
Quick custom-sort reminder (Python)
people.sort(key=lambda p: (-p.age, p.name))
Written by the Linkjob AI team. For timed practice we build AI help for online coding assessments.