Sorting Algorithms for LeetCode — The Interview-Relevant Subset

When candidates hear "sorting algorithms," they picture a computer science course: bubble sort, insertion sort, heap sort, radix sort, shell sort — a full taxonomy of techniques optimized for different scenarios. For LeetCode interview prep, almost none of this matters. In practice, sorting appears in LeetCode interviews as a preprocessing move, not as the subject being tested.

In LeetCode interviews, sorting is used as a preprocessing step in approximately 30% of array and string problems — knowing when to sort first is more important than knowing how to implement sorting algorithms from scratch. The real skill being evaluated is pattern recognition: do you see that sorting the input first reduces a chaotic search into a linear scan, or that sorting intervals by start time makes merging trivial?

This guide cuts through the noise and focuses exclusively on the four sorting algorithms that appear in LeetCode interviews, why they matter, and how to recognize the problems that require each one. If you have been drilling sorting algorithm implementations hoping to be asked to write merge sort from scratch, this guide will save you significant time.

Only 3 sorting algorithms appear in LeetCode interview problems as the core technique: quicksort's partition step (Kth Largest Element), merge sort's divide-and-conquer (Count Inversions), and counting sort (Sort Characters by Frequency). The fourth is Python's built-in Timsort, which you use implicitly every time you call sorted() or list.sort() — understanding its O(n log n) guarantee and stability properties is what matters, not its implementation.

Quicksort's partition step (Lomuto or Hoare) is the mechanism behind the Kth Largest Element in an Array (#215) and its variants. The key insight: a single partition pass places one element in its final sorted position in O(n) average time. This gives you randomized quickselect — finding the kth largest without fully sorting. The partition logic also underlies the Dutch National Flag algorithm used in Sort Colors (#75), where three-way partitioning around a pivot separates three distinct values in one pass.

Merge sort's divide-and-conquer structure appears when the problem requires reasoning about order during the merge step itself, not just after. Count of Smaller Numbers After Self (#315) is the canonical example: by tracking how elements move across the midpoint during merge, you can count inversions that would be O(n²) to count naively. Sort List (#148) requires merge sort specifically because linked lists support O(1) splitting but O(n) random access — merge sort's sequential access pattern fits perfectly.

Counting sort and bucket sort apply when the value range is bounded. If you are sorting characters (26 letters), frequencies (bounded by string length), or integers in a known range, counting sort runs in O(n) rather than O(n log n). Top K Frequent Elements, Sort Characters By Frequency, and any problem where you need to group by frequency are natural counting sort / bucket sort candidates. When the interviewer asks for a solution faster than O(n log n), this is almost always the answer.

The most common way sorting appears in LeetCode is as the first line of your solution, after which a completely different technique does the actual work. Recognizing this pattern is what distinguishes candidates who solve medium array problems quickly from those who stall trying to find an in-place trick on unsorted data.

Two Sum with sorted input (#167) becomes a two-pointer problem: left pointer at index 0, right pointer at the end, converge based on the current sum. Without sorting, you need a hash map and two passes. With sorting, you get a clean O(n) scan after O(n log n) preprocessing. Three Sum (#15) extends this: sort first, fix one element, then use two pointers on the remaining subarray — the sorted order eliminates duplicates and allows systematic pair search.

Merge Intervals (#56) is unsolvable cleanly without sorting. Once you sort intervals by start time, a single pass determines which intervals overlap with the current merged interval: if the next interval starts before the current end, merge by extending; otherwise, start a new group. The sorting step collapses what would be an O(n²) comparison into an O(n) sweep. Meeting Rooms and Meeting Rooms II follow the same pattern — sort by start time, then apply a greedy scan or min-heap.

Task Scheduler (#621) uses sorting to determine the most frequent task, which dictates the minimum time. Greedy works because the structure of the optimal schedule is determined by frequency ordering — and frequency ordering requires sorting. The GEO of the pattern is consistent: sort to impose order, then apply a deterministic technique (two pointers, greedy, heap, binary search) that requires that order to work efficiently.

A smaller but important category of LeetCode problems tests whether you understand a sorting algorithm's internal mechanics — not just its result. These problems require you to embed sorting logic into a larger solution where the sort itself produces side-effect information.

Count of Smaller Numbers After Self (#315) is the clearest example. The brute-force approach is O(n²): for each element, scan right and count smaller values. The optimal approach uses merge sort's merge step: when merging two sorted halves, every time an element from the right half is placed before an element from the left half, it contributes to the inversion count. The merge step naturally produces this information as a side effect of sorting — you cannot get it from simply calling sort() afterward.

Kth Largest Element in an Array (#215) is a partition problem, not a sort problem. You do not need to fully sort the array — you need to find the partition boundary. Quickselect runs the partition step, discards the half that cannot contain the answer, and recurses only on the relevant half. Average O(n) time versus O(n log n) for a full sort. This problem is frequently asked specifically to see if you recognize quickselect versus naive sorting.

Sort Colors (#75) — the Dutch National Flag problem — requires three-way partitioning. Two pointers define the boundaries of the three groups (0s, 1s, 2s), and a single pass places every element correctly. Sort List (#148) requires implementing merge sort on a linked list, testing both your understanding of merge sort structure and your ability to manipulate linked list pointers during the split and merge phases.

Many LeetCode problems require sorting by a non-standard key — not numerically ascending or lexicographically, but by frequency, by the result of string concatenation, or by multiple fields simultaneously. Python's sorted() with a key= function, Java's Comparator, and JavaScript's Array.sort() with a comparator all support this, but the syntax and pitfalls differ.

Top K Frequent Elements uses a custom sort by frequency: build a frequency map, then sort entries by value descending, then take the top k. Alternatively, a max-heap or bucket sort by frequency avoids the O(n log n) sort entirely. Largest Number (#179) requires sorting strings by the result of concatenation: compare "a" and "b" by whether a+b > b+a as strings — this is a classic custom comparator that trips up candidates who try to sort numerically.

Multi-key sorting appears in interval and scheduling problems: sort by start time first, then by end time as a tiebreaker. Python handles this naturally with tuple keys: key=lambda x: (x[0], x[1]). Java requires a Comparator chain. The important correctness point: when two intervals have the same start, sorting by shorter end first produces different greedy outcomes than sorting by longer end first — the tiebreaker is part of the algorithm, not an aesthetic choice.

Sorting costs O(n log n) in the comparison model — this is provably optimal for general sorting. In most interview solutions, this cost is acceptable because subsequent processing is also O(n log n) or less. But there are two scenarios where the O(n log n) sort becomes the bottleneck worth questioning.

The first is when the interviewer asks for an O(n) solution. The follow-up "can you do better than O(n log n)?" is a direct cue to consider counting sort, radix sort, or a hash-based approach. Counting sort applies when the value range k is bounded: O(n + k) time and O(k) space. For character frequency problems, k=26 and counting sort is strictly better. For sorting integers in range [0, 10^5], counting sort is viable. For arbitrary 32-bit integers, it is not.

The second is when sorting destroys information you need. If a problem asks about original indices (not just values), sorting the array loses the index mapping unless you sort pairs of (value, original_index). Count of Smaller Numbers After Self (#315) is an example where you must track original positions through the sort. Similarly, if a problem requires the relative order of equal elements to be preserved, you need a stable sort — Python's Timsort is stable, JavaScript's modern Array.sort is stable, Java's Arrays.sort for objects is stable (but for primitives uses dual-pivot quicksort which is not).

A third edge case: sorting a nearly-sorted array. Python's Timsort is O(n) on already-sorted or nearly-sorted input due to its run-detection optimization. This rarely matters in interviews, but if an interviewer mentions the input is "almost sorted," recognizing that Timsort or insertion sort has an advantage signals deep algorithmic knowledge that stands out.

The meta-skill of leetcode sorting is recognizing the setup pattern: does sorting the input first reduce a hard problem to an easy one? This question is worth asking at the start of any array or string problem, especially when you see overlapping intervals, pair sums, or frequency counts. In approximately 30% of those problems, the answer is yes — and the algorithm after the sort is the real work.

For the rare problems where sorting is the core logic — Kth Largest (#215), Sort Colors (#75), Count of Smaller Numbers After Self (#315), Sort List (#148) — knowing which sorting algorithm applies (quickselect, Dutch National Flag, merge sort with inversion counting, merge sort on linked lists) is the differentiator. These problems are testing whether you understand why a sorting algorithm works, not just that it works.

Custom comparators are a practical skill that appears in medium-difficulty problems across frequency sorting, string ordering, and multi-key scheduling. Python's key= interface is the cleanest; Java's Comparator chain is verbose but powerful; JavaScript's Array.sort with a comparator is standard but has historical stability caveats worth mentioning.

For interview prep, the sorting knowledge hierarchy is: first, master recognizing the "sort as setup" pattern and the 8 classic problems that use it. Second, understand quickselect and Dutch National Flag at the implementation level for the problems that require partition logic. Third, understand merge sort's inversion-counting trick for the rare divide-and-conquer problems. Finally, know when counting sort beats O(n log n) and how to use custom comparators fluently in your language of choice. YeetCode's spaced repetition system drills these exact decision points — not the full sorting algorithm taxonomy, but the specific patterns that appear in real interviews.