Sorting

You already call std::sort without thinking twice. This topic is about what's underneath that call, and — more importantly — when reaching for it isn't actually the fastest option. Comparison-based sorting (the kind std::sort does) has a hard, provable floor: no algorithm that only compares pairs of elements can sort in better than O(n log n) time, in the worst case, ever. But several of this topic's problems beat that floor entirely, because they aren't really comparison problems in disguise — they're counting problems, or partitioning problems, that happen to look like sorting.

Comparison sort, implemented: merge sort's guarantee

Sort an Array asks you to build a sort yourself. Merge sort earns its place as the default teaching example over quicksort for one concrete reason: quicksort's O(n log n) is an average, and a bad pivot choice degrades it to O(n^2) in the worst case, while merge sort's divide-exactly-in-half recursion structure guarantees O(log n) levels no matter what the input looks like. That reliability is also why std::stable_sort is typically merge-sort-based under the hood, while std::sort usually leans on a quicksort variant with fallbacks. Sort List asks the same question with one constraint removed: a linked list has no random access, so finding the midpoint needs its own technique (the slow/fast pointer trick) before the same divide-and-merge structure applies.

Partial sorting and constrained operations

Kth Largest Element doesn't need the whole array sorted — it needs one position. Quickselect reuses quicksort's partition step but discards the side that can't contain the answer, turning O(n log n) into O(n) on average. Sort Array by Parity is the simplest version of the same idea: partitioning isn't sorting, but it's often all a problem actually needs. Pancake Sort flips the question around entirely — instead of asking "how do I sort fastest," it asks "how do I sort at all, using only this one restricted operation (reversing a prefix)?" The answer (repeatedly moving the current max to the front, then flipping it into place) is a reminder that sorting algorithms are shaped as much by what operations you're allowed as by what's fastest.

Custom comparators — and the trap of assuming numeric order

Largest Number is the clearest lesson in this topic on why "sort descending" isn't always well-defined without saying descending by what. Comparing 3 and 30 numerically puts 30 first — but "330" loses to "303" as a concatenated number. The fix is a comparator that directly answers the question that matters: does a + b or b + a produce the larger string? Relative Sort Array and Custom Sort String need a "sort by this other order" too, but their answer is different: since their value ranges are small and fixed (0–1000; the 26 lowercase letters), counting sort with a custom bucket sequence beats a comparator-based sort outright, at O(n + k) instead of O(n log n).

Beating O(n log n): counting, bucketing, and pigeonholes

This is where the "sorting" label gets misleading. Relative Sort Array and Custom Sort String both need a "sort by this other order," and since their value ranges are small and fixed (0–1000; the 26 lowercase letters), counting sort with a custom bucket sequence beats a comparator-based sort outright, at O(n + k) instead of O(n log n). Maximum Gap is the sharpest example: it needs the largest gap between sorted-adjacent elements, but never needs the full sorted order to get there. Splitting the value range into exactly n−1 buckets guarantees — by the pigeonhole principle — that at least one bucket is empty, which means the true maximum gap can only occur between buckets, never within one. That turns an O(n log n) sort into an O(n) scan of bucket boundaries.

When sorting first turns a hard question into an easy scan

H-Index and Third Maximum Number both show that a full sort isn't always the cheapest way to use "sortedness." H-Index sorts citations descending, then a single linear scan finds the crossover point — turning a question that sounds combinatorial ("how many papers have at least this many citations?") into one pass over already-ordered data. Third Maximum Number skips sorting entirely: since only the top 3 distinct values ever matter, tracking three running values in one pass beats an O(n log n) sort outright — the same "you don't need the whole order, just a small piece of it" idea as quickselect, taken to its logical extreme. Wiggle Sort II shows the "sort first" instinct needs a real subtlety on top: sorting and then naively interleaving front-to-back breaks the moment there are duplicate values, and the fix — filling both halves back-to-front — is specifically what keeps equal values from landing adjacent to each other.

Common mistakes

• Assuming quicksort's average case is its worst case — an adversarial or already-sorted input can degrade naive quicksort to O(n^2); merge sort's guaranteed O(n log n) is why it's the safer default when a real worst-case bound matters.
• Comparing numbers numerically when the real question is about concatenation — Largest Number's a + b > b + a comparator exists specifically because numeric or length-based comparisons give the wrong order.
• Reaching for a full sort when only a rank, boundary, or a handful of top values is actually needed — Kth Largest, Sort Array by Parity, and Third Maximum Number are all faster without ever producing a total order.
• Interleaving a sorted array front-to-back for Wiggle Sort — this looks reasonable but places equal adjacent values next to each other the moment duplicates are heavy; filling both halves back-to-front avoids it.
• Using a same-width sentinel value to mean "not set yet" — Third Maximum Number's classic trap is using INT_MIN as an int placeholder for "no value yet," which collides with an array that genuinely contains INT_MIN; a wider sentinel type sidesteps the collision.
• Missing that a small, fixed value range means counting sort beats comparison sort — Relative Sort Array and Custom Sort String are both faster at O(n + k) than a general O(n log n) comparator sort, once the range is bounded by something smaller than n.