When sorting first is worth it — every question, written out
The n log n tax and the problems it makes trivial — and the ones where it is strictly wasted work.
Sorting first costs O(n log n). Where does that floor actually come from?
Complexity derivation
n! orderings exist and each comparison halves the candidates, so about log₂(n!) ≈ n log n comparisons are needed
A comparison learns one bit, and the sort must distinguish n! possible input orderings. That needs at least log₂(n!) comparisons, which Stirling’s approximation puts at roughly n log n. The floor is about information rather than implementation, which is exactly why counting sort can beat it — it never compares two elements at all.
Sorting turns "does this array contain a duplicate?" into a one-pass adjacency check. When is that the wrong call?
Trade-off & selection
When memory is available: a hash set answers in O(n) and stops at the first repeat
Sorting makes duplicates neighbours, so one adjacent-pair scan finds them — a clean O(n log n) solution that needs no extra space. A hash set does the same job in expected O(n) and bails out the moment a value repeats, at the cost of O(n) memory. Sort when memory is the binding constraint or the data is already ordered, and hash otherwise.
Find the smallest absolute difference between any two values in an unsorted array. Why does sorting make this trivial?
Comparison
After sorting, the closest pair must be adjacent, so one pass over neighbouring pairs suffices
Sorting converts a quadratic all-pairs search into a linear scan, because values close in magnitude end up close in position. The argument is one line: if x and y were the closest pair and some value sat between them, that value would be closer to both. Total cost is the sort, and the scan afterwards is free by comparison.
You need the k-th largest of n values, once, with k far smaller than n. What does sorting cost you?
Trade-off & selection
A full ordering you never use — a size-k heap gives O(n log k), quickselect gives O(n) on average
Sorting answers "what is the full order?" when the question was "what is one element?", so nearly every comparison is discarded. A max-heap makes the distinction visible: it promises only that each parent beats its children, and that partial order is enough to hand you extremes one at a time. Keep a size-k heap for O(n log k), or use quickselect for expected O(n) when the input may be reordered.
See it run — The build finishes and the annotation says it: the second level is NOT sorted, yet the maximum is known.
Merging overlapping intervals begins by sorting on start time. What invariant does that buy the one-pass loop?
Invariant identification
A new interval can only ever overlap the most recent block, so every earlier block is sealed
Sorted starts mean no later interval can begin before the current block began, so nothing can reach back past the last block. That one guarantee collapses an all-pairs overlap check into a single comparison per interval. Prism states it on the opening step of the merge-intervals run: the sort is the entire licence for the one-pass merge.
See it run — The annotation names the sorted order and calls the sort the licence for everything after it.
A candidate sorts the array and returns `a[0]` to find the minimum. What is wrong with it?
Edge case reasoning
It pays O(n log n) for an answer that a single linear scan already gives in O(n)
Sortedness is stored work, and this code buys the whole warehouse to take one item off a shelf. A single pass tracking the smallest value seen answers in O(n) with O(1) space and without touching the caller’s array. The habit worth building is asking what the problem actually needs before reaching for a sort.
One membership query against an unsorted array. Is sorting first and then binary searching ever the better plan?
Complexity derivation
No — O(n log n + log n) is strictly worse than the O(n) linear scan it replaces
The rule is: do not buy order you will spend once. Sorting costs O(n log n) up front and one logarithmic query cannot recover it, so the naive scan wins outright. The arithmetic flips as soon as the queries multiply, which is the next question to ask rather than this one.
Now suppose q membership queries hit the same static array. Where is the crossover?
Complexity derivation
Around q ≈ log n: sorting costs n log n + q log n, while scanning costs q·n
Setting n log n + q log n against q·n gives a crossover a little above q = log n, which for realistic n is a handful of queries. That is why "sort once, then binary search" is the standard shape for static lookup tables, and why nobody sorts for a single query. The same arithmetic is what makes a database index worth building.
Two values summing to a target: hash map in O(n), or sort and then walk two pointers in O(n log n)?
Comparison
Hash map, unless memory is tight or the array is already sorted — then two pointers win
The hash map needs no order and runs in expected O(n) with O(n) memory; two pointers need order and run in O(n) with O(1) memory once the array is sorted. If the input arrives sorted the sort vanishes from the bill, and two pointers are simply better. Naming both and then choosing is the expected answer — that reasoning is what is graded, not the code.
See it run — The invariant spells out the elimination: too large a sum condemns a[17] against every remaining partner.
What must be true of the data before a sort can legitimately run in linear time?
Complexity derivation
The keys must be usable as addresses — a small integer range, or fixed-width digits
The n log n floor applies to sorts that learn only by comparing, so the escape is to stop comparing. Counting and radix sorts use the key itself as an index into a tally table, which is why their cost is O(n + k) in the size of the key space rather than in comparisons. Prism says it on the first step of a counting-sort run: the values themselves are the addresses.
See it run — The annotation prices the escape — 17 tally slots for 16 values, and that "+k" is the whole trade.
Kruskal’s algorithm sorts every edge by weight before taking any. What breaks if it does not?
Invariant identification
The greedy choice loses its justification — a taken edge may belong to no minimum spanning tree
Sorting is what makes "take it unless it closes a cycle" safe: the lightest edge crossing any cut belongs to some minimum spanning tree, and weight order is how that cut property gets honoured. Drop the order and the run still yields a spanning tree, just not a minimum one. Prism prices the sort on the opening step — it is where the O(E log E) lives.
See it run — Twelve edges listed in weight order, before a single one has been considered.
The answer must be the original positions of two elements, and you sorted the array to find them. Now what?
Edge case reasoning
You needed to carry each index alongside its value, because sorting destroyed the mapping
Sorting rearranges values and throws away where they came from, so any problem whose answer is an index must carry that index as part of the record. The usual shapes are sorting pairs of value and index, or sorting an array of indices by the value each one points at. Noticing this before writing the sort is what separates a working two-sum from one that returns the right numbers at the wrong places.
Prism sorts 16 nearly-sorted values with insertion sort in 179 steps. What does the reversed preset take?
Trace prediction
521 steps — insertion sort pays per inversion, and reversal maximises the inversion count
Insertion sort runs in O(n + inversions), so its cost measures how disordered the input already is rather than how large it is. Prism records 176 steps on sorted input, 179 on nearly sorted, 348 on random and 521 on reversed — the same 16 elements, a threefold spread. Merge sort over those same presets stays between 446 and 462 steps, which is what non-adaptive looks like.
See it run — The invariant names the sorted prefix; watch how few shifts each key needs on this preset.
Grouping anagrams sorts the letters inside each word. What is the sort actually doing there?
Trade-off & selection
Producing a canonical key, so that any two anagrams land in the same hash bucket
Sorting is being used as a normalising function rather than to order anything: two words are anagrams exactly when their sorted letters are identical, so the sorted string is a key. The whole grouping then costs O(m · L log L) for m words of length L, with one hash-map insert each. A letter-count tuple is the same trick without the log factor, and is what you would reach for if L were large.
In JavaScript, `[10, 9, 100].sort()` returns `[10, 100, 9]`. What went wrong, and what does it cost?
Code diagnosis
The default comparator orders by string, so every later step assuming numeric order is wrong
`Array.prototype.sort` converts elements to strings and compares them lexicographically unless a comparator is supplied, so "100" sorts before "9". The failure is silent, which is the dangerous part: a binary search or two-pointer pass over this array returns confident nonsense rather than an error. Passing `(a, b) => a - b` makes it disappear.
Values arrive continuously and you must always be able to name the current smallest. Why is sorting the wrong tool?
Edge case reasoning
Re-sorting on every arrival costs n log n each time; a heap holds the extreme at log n per insert
The question is not "how do I get order?" but "how do I maintain it as things change?", and those have different answers. A heap gives O(log n) insertion and O(1) access to the extreme precisely because it promises only the parent-child relation, never a total order. When the full order must be maintained rather than just the extreme, that is what a balanced tree is for.
One value occupies more than half the array. Sorting and reading the middle works — what beats it?
Comparison
Boyer–Moore voting: one candidate, one counter, a single pass, O(n) time and O(1) space
Sorting works and is a respectable first answer, but it buys a total order to extract a single fact that one pass can maintain. Boyer–Moore keeps a candidate and a count, cancelling a matched pair of differing values each time, and only a true majority element can survive that cancellation. It runs in O(n) time and O(1) space, and the majority guarantee is exactly what makes it correct.
Explain to someone who does not code why sorting a list first can make a later question much easier. Say it out loud before revealing.
Explain it plainly
Picture a shelf of unlabelled folders in no particular order. Right now, to answer almost anything — is there a duplicate, which two are most alike, is this one here at all — you have to look at every single folder, because the one you have not checked could always be the one. Now spend an afternoon putting them in order. That afternoon is not free, but afterwards a whole class of questions collapses: duplicates are sitting next to each other, so you walk the shelf once; the two most similar are neighbours, so there is no cross-checking; and to find one folder you open the middle, see which way to go, and throw away half the shelf with every look. The order is doing work you would otherwise repeat every time you were asked. The catch is that the afternoon only pays off if you are going to ask a lot of questions. If all you ever need is the very first folder alphabetically, just walk the shelf once and take it — sorting the whole cabinet to answer one question is buying a filing system to find a single page.
The listener should come away with sortedness as stored work rather than as tidiness. A strong answer gives one concrete question that becomes easy after ordering, and — the part most people skip — names a question where sorting would be pure waste.