Preview — Pro guide
You are seeing a portion of this guide. Sign in and upgrade to unlock the full article, quizzes, and interview answers.
Sorting Algorithms: Merge Sort, Quickselect, and Custom Comparators
Sorting for FAANG interviews: when to sort, when to use counting/radix sort, how merge sort counts inversions, and how Quickselect finds Kth largest in O(n) average. Covers the comparison-sort lower bound and Python custom comparators.
When Sorting Actually Matters in Interviews
Sorting is almost never the point of a problem — it's a preprocessing step that unlocks a faster algorithm. Understanding which problems need sorting, and why, is more valuable than memorizing sort implementations.
Pattern 1 — Sort as preprocessing for two-pointer or binary search. Two-sum with sorted input, three-sum, merge intervals, container with most water — these are O(n²) or worse without sorting, O(n log n) with. The key: sort first, then apply the simpler algorithm. If the problem requires you to find pairs satisfying a constraint, ask 'does sorting + two-pointer beat brute force?' In almost all cases, yes.
Pattern 2 — Custom comparator for non-obvious orderings. 'Largest Number' (LC 179), 'Meeting Rooms II', 'Task Scheduler' — these require a sort order that isn't numeric ascending. You define the comparison function and let the sort engine do the work. The trap: the comparator must be transitive (if a > b and b > c, then a > c). Violating transitivity produces undefined behavior — wrong answers that vary by input order.
Pattern 3 — Sort to make greedy work. Activity selection (sort by end time), interval scheduling, fractional knapsack (sort by value/weight ratio), Huffman coding — greedy correctness proofs almost always rely on the sorted property. Without sorting first, greedy makes locally optimal choices that aren't globally optimal.
Sorting is O(n log n) and often negligible. The signal that sorting is the wrong tool: when the problem has structure that allows O(n) — bounded integers, fixed alphabet, or a specific distribution.
Sorting Problem Recognition Framework
Is the problem asking for pairs, triplets, or ranges?
Sorting as preprocessing converts O(n²) brute-force pair-search into O(n log n + n) with two-pointer. Classic: Two Sum II, Three Sum, Container With Most Water, Merge Intervals. Signal: 'find all pairs where A[i] + A[j] = target'.
Does the problem need a non-obvious ordering?
If objects must be ordered by a derived property (not just by value), sort with a custom comparator. Signal: 'arrange to maximize/minimize some combination'. Examples: Largest Number (LC 179), Task Scheduler, sort by meeting end time for greedy interval scheduling.
Is greedy involved? Does it need a sorted precondition?
Most greedy algorithms require the input to be sorted to prove correctness. Activity selection: sort by end time. Fractional knapsack: sort by value/weight ratio. Minimum cost to connect ropes: sort and use min-heap. If you're writing a greedy algorithm, ask: what sorted order makes the greedy choice always optimal?
Are the values bounded integers? Can you beat O(n log n)?
If elements are integers in a small range [0, k), counting sort gives O(n + k). If sorting fixed-width integers, radix sort gives O(dn). Ask: 'what is the value range?' before defaulting to comparison sort. If k = O(n), O(n) sort is possible.
Do you need Kth element without full sort?
If the problem asks for the Kth largest/smallest element (not all elements sorted), Quickselect is O(n) average vs O(n log n) for sort. Heap gives O(n log k). For k = 1 (min/max), a single linear scan is O(n). Always match the tool to the output needed.