Algorithms · interview field notes

Why is sorting O(n log n) — and how do you prove it's optimal?

Two questions a senior interviewer will press on. This is a guided walk-through — press Play on each figure, step at your own pace, and leave able to say the answer, not just recall it.

Why is sort O(n log n)? Does it apply to every Ruby sort?

How do I know it's optimal — that no better algorithm exists?

The answer to memorize

Comparison sorts have a proven floor

The one sentence to keep in your pocket — say it cleanly and stop:

Say this

"Comparison-based sorting has a proven lower bound of Ω(n log n) — you can't sort by comparing elements faster than that. Ruby's sort / sort_byare comparison sorts, so they're O(n log n)."

That's the whole answer. The rest of this page is why it's true and how to wield it — so that when an interviewer pushes, you have the proof, not just the claim. Two separate ideas are at play: where the n log n comes from in an actual algorithm, and why nothing can ever beat it.

Watch it happen

Where the n log n comes from

Forget formulas for a second. Run an actual comparison sort — merge sort — and the n log n falls out of its shape: a handful of passes, each one a single sweep across the data.

Merge sort · passes × workfig

tip — click any merged run to step into the merge that built it

start

width 1

n = 8

elements

log₂n = 0

passes · of 3

comparisons so far

We start with 8 singletons — each one element, trivially sorted. Merge sort now merges neighbours in passes.

01 / 05

log₂n passes × n work per pass = n log n. That's the upper bound — proof a sort this fast exists. Next: proof you can't do better.

The senior skill

Why nothing beats it: the decision tree

Here's the proof, and it's the part that makes you sound senior. Any comparison sort is really a tree of yes/no questions. Counting the leaves gives the floor.

The sorting decision tree · n = 3fig

orderings to distinguish≤ 6

a < b < ca < c < bc < a < bb < a < cb < c < ac < b < a

There are 3! = 6 possible orderings of three items. A comparison sort doesn't know which is right — it must distinguish all six.

01 / 05

n! orderings → each comparison halves them → need log₂(n!) ≈ n log n comparisons

If an interviewer pushes "why log₂(n!)?"

"There are n! possible orderings; each comparison splits the remaining possibilities in half, so you need about log₂(n!) ≈ n log n comparisons to pin down the right one." You don't prove it — you name it.

Transfer the floor to your problem

Is your problem as hard as sorting?

The decision tree bounds sorting. But your interview problem is merge-intervals. The elegant move: show your problem could be used to sort — so it inherits sorting's floor.

Reduction · sorting ⤳ merge-intervalsfig

unsorted input

528163

step 2 · merge-intervals orders them on the line

Here's the trick that pins down the difficulty. Take any list of numbers you want to sort.

01 / 05

Proving optimality

Optimal = match the floor

You don't prove optimality by enumerating every possible algorithm. You prove a lower bound and check whether your algorithm touches it. Two numbers, done.

Lower bound vs. your algorithmfig

"Can this be optimized?" Don't enumerate algorithms — answer with two numbers: the floor, and where your algorithm lands.

01 / 04

Say this when asked "can this be optimized?"

"Reading the input is Ω(n), and the problem is as hard as sorting, so Ω(n log n) — my solution matches that, so it's optimal."

The payoff clarifier

Same problem, different floor

The lower bound isn't a property of the problem name — it's a property of the input. Flip the assumption and watch the floor move. This is why "is it sorted?" is a great question to ask up front.

Same problem · different floorfig

Unsorted. The problem is as hard as sorting, so the floor is Ω(n log n) — you pay for the sort.

same merge-intervals problem — the input's structure moves the floor

Print this on the back of your hand

The interview cheat-sheet

“Why is sort O(n log n)?”

Comparison sorting has a proven lower bound of Ω(n log n). Ruby's sort/sort_by are comparison sorts → O(n log n), worst and average.

“Why that lower bound?”

n! orderings; each comparison halves the possibilities → need log₂(n!) ≈ n log n comparisons. Name it; don't prove it.

“How do you know it's optimal?”

Prove a lower bound and match it. Floor = Ω(n log n) (reading input is Ω(n); problem is as hard as sorting). My algorithm is O(n log n) → it matches → optimal.

“Could it be faster?”

Only if the input is already sorted — then the floor drops to Ω(n) and a single O(n) pass suffices. Otherwise, no.

Senior bonus — don't lead with it

Non-comparison sorts (counting / radix) can hit O(n) when keys are bounded integers — which permit-days actually are. But Ruby's built-in sort is a comparison sort, so the safe, correct answer stays O(n log n). Only mention radix if an interviewer explicitly asks "can you beat n log n?"