skip to content

How do you write a multi-key Less for sort.Interface so ties fall back to a second field?

level: middleimportance: must knowfreq 64%

answer

  1. one bool, several keys
  2. each key needs its own guard
  3. differ then return, equal then fall through
  4. joining keys with || breaks symmetry
  5. finish on a unique id

basics

~20 s

Compare one key at a time: if the primary fields differ, return that comparison; otherwise fall through to the next field, and end with a unique tie-breaker. Never join key comparisons with || or &&, which produces an inconsistent ordering.

solid answer

~50 s

A `Less` returns a single bool, so a multi-key ordering has to be written as a cascade rather than one expression. For each key in priority order: if the two values differ, return the comparison for that key; if they are equal, fall through to the next key. Finish with a field that is unique — an id — so no two distinct rows are ever reported equal, which makes the output deterministic without relying on the sort's behaviour for ties. The bug to watch for in review is `return a.Score > b.Score || a.Name < b.Name`: the second clause is evaluated even when the scores differ, so the method can report both `Less(i, j)` and `Less(j, i)` true. Mixing directions is fine — the cascade can use `>` for one key and `<` for the next.

code

go · 10 lines
go
func (r byRank) Less(i, j int) bool {
	a, b := r[i], r[j]
	if a.Score != b.Score {
		return a.Score > b.Score
	}
	if a.Region != b.Region {
		return a.Region < b.Region
	}
	return a.ID < b.ID
}

go deeper

for a junior

Be able to write the cascade: test whether the first key differs, return that comparison, otherwise move to the next key. Know that the method returns one bool, so the keys cannot be combined into one expression.

for a middle

Explain precisely why the || form is wrong — the lower-priority clause still runs when the higher-priority one is false — and show that different keys may sort in different directions inside the same cascade.

for a senior

Bring the production angle: precomputed sort keys instead of work inside Less, a unique final tie-breaker so the rendered order is reproducible, NaN handling on float keys, and a pair-level unit test that asserts symmetry and transitivity.

for a principal

Own where the ordering lives. A ranking rule encoded in one comparison method deep in a renderer is invisible to the people who define it; decide whether the key list is configuration, a documented package-level type, or duplicated in three services with subtly different tie-breakers.

## Why a cascade, not one expression `Less(i, j int) bool` answers one question: does element `i` sort before element `j`? With several ranking keys you are really asking a sequence of questions, and each one is only allowed to decide the outcome when all the higher-priority keys tie. Because the method returns a single bool, that sequence has to be spelled out as early returns: ```go type byRank []Row func (r byRank) Less(i, j int) bool { a, b := r[i], r[j] if a.Score != b.Score { return a.Score > b.Score // highest score first } if a.Region != b.Region { return a.Region < b.Region } return a.ID < b.ID // unique tie-breaker } ``` Read it as: *decide on Score if you can; otherwise decide on Region if you can; otherwise decide on ID.* Every key gets its own equality test guarding its own comparison, and directions can differ per key — descending Score with ascending Region, as above. ## The `||` bug The expression that looks like it should work is: ```go return a.Score > b.Score || a.Region < b.Region // WRONG ``` Go's `||` does short-circuit, so the second clause is skipped when the first is true — but it is *evaluated whenever the first is false*, including when `a.Score < b.Score`. Take a row with a high score in region `"west"` and a row with a low score in region `"east"`. Comparing them one way, the score decides. Comparing them the other way, the score clause is false, the region clause fires, and the method claims the *other* row sorts first. Both `Less(i, j)` and `Less(j, i)` are true. The ordering is no longer consistent, and the resulting order is arbitrary. The same is true of `&&`, which drops rows out of the ordering rather than double-counting them. The guard-and-return cascade is the only shape that works. ## Ending with a unique key A cascade whose last key can still tie leaves genuine equals, which is fine but means `sort.Sort` may place them in any order — two runs over the same data can render a report's tied rows in different positions, and a golden-file test then flakes. Two ways out: end the cascade on a field that is unique per row (an id, a source line number), or use `sort.Stable` so equal rows keep their input order. Choosing a unique final key is usually cheaper to reason about, because the ordering is then total and the result does not depend on which sort function the caller used. ## Keeping the cascade cheap and correct A few practical points for review: - **Bind the two elements once.** `a, b := r[i], r[j]` at the top reads better than repeating `r[i].Field` on every line, and for a small struct the copy is negligible. If the struct is large, take pointers instead: `a, b := &r[i], &r[j]`. - **Do not do expensive work inside `Less`.** It runs on the order of `n log n` times. Parsing a timestamp, lowercasing a string or formatting a value per comparison is a classic report-renderer hot spot; precompute the sort key into a field before sorting instead. - **Do not read mutable shared state.** `Less` must give the same answer for the same pair throughout the sort. A comparison that consults a counter, a clock, or a map another goroutine writes is not an ordering at all. - **Watch NaN.** For a `float64` key, `<` is false in both directions when either value is NaN, so NaNs are reported equal to everything, and the ordering stops being transitive. Filter or normalise them before sorting. - **Comparing strings case-insensitively** means calling something like `strings.EqualFold` for the equality guard and a case-folded comparison for the ordering — do not mix a case-sensitive guard with a case-insensitive comparison, or the guard and the decision disagree. ## Reviewing one The fast check on any multi-key `Less` is to read it as a decision table and ask, for each key, *can this line run when a higher-priority key already decided?* If the answer is yes for any line, the ordering is broken. A cheap unit test does the same job mechanically: for a handful of representative rows, assert that `Less(i, j)` and `Less(j, i)` are never both true, and that transitivity holds across triples.

  • Why is `return a.Score > b.Score || a.Region < b.Region` wrong even though || short-circuits?
    Short-circuiting only skips the second clause when the first is *true*. When `a.Score < b.Score` the first clause is false, so the region clause runs and can claim `a` sorts first anyway. Compare the same pair in both directions and the method answers true both times, which no consistent ordering can do.
  • Can different keys in one Less sort in different directions?
    Yes, and that is the main reason to write the cascade by hand. Each guarded return chooses its own operator, so `Score` can use `>` for descending while `Region` uses `<` for ascending. Wrapping the whole thing to flip direction cannot express that, because it flips every key at once.
  • What would you do if a sort key is expensive to compute from the row?
    Precompute it into a field before sorting. `Less` is called on the order of n log n times, so parsing a timestamp, folding case or formatting a number inside it multiplies that cost across every comparison. Materialise the derived key once per row, sort on the field, and drop it afterwards if it is not part of the output.
  • How do you unit-test a multi-key Less?
    Test the method directly rather than only the sorted output. For a small set of representative rows, assert that `Less(i, j)` and `Less(j, i)` are never both true, that transitivity holds for triples, and that a hand-written expected order comes back from the sort. That catches an ordering bug at the pair level, where the failure is readable.

saying these in an interview costs you the question

  • Joins key comparisons with || or && in one return
  • Uses <= for the primary key so ties compare both ways
  • Compares the second key without first testing the first for equality
  • Does expensive parsing or formatting inside Less
  • Assumes a float64 key with NaN still gives a transitive ordering