skip to content

Why does slices.SortFunc take a comparison returning an int rather than a bool?

level: middleimportance: should knowfreq 55%

answer

  1. only the sign is read
  2. three outcomes, not two
  3. the zero case carries information
  4. ties are what a stable sort needs
  5. the same function also drives the search

basics

~20 s

slices.SortFunc's callback returns a negative, zero or positive int meaning a sorts before, equal to, or after b. The three-way result reports equality, which a boolean less-than cannot, so one function can also drive stable sorting and binary search.

solid answer

~40 s

`slices.SortFunc(x, cmp)` calls `cmp(a, b)` and reads the **sign** of the returned `int`: negative means `a` sorts before `b`, positive means after, and **zero means the two are equal for ordering purposes**. A boolean less-than only answers one of those three questions - to learn that two elements are equal you would have to call it twice. Zero is load-bearing: `slices.SortStableFunc` needs it to know which elements are ties worth keeping in input order, and `slices.BinarySearchFunc` and `slices.IsSortedFunc` consume the very same three-way shape, so a single comparison function can serve sorting, checking and searching. The function must be a consistent ordering - antisymmetric and transitive - or the result is undefined. Two habits break it: never returning zero, and writing `return a - b` for integers, which gives the wrong sign on overflow.

code

go · 14 lines
go
type user struct {
	Name string
	Age  int
}

slices.SortFunc(users, func(a, b user) int {
	if a.Age < b.Age {
		return -1
	}
	if a.Age > b.Age {
		return 1
	}
	return 0 // equal ages: report the tie
})

go deeper

for a junior

Be ready to write the callback: return a negative number when the first argument sorts first, a positive number when it sorts later, and zero when they tie. Know that slices.SortFunc is what you use for structs.

for a middle

Explain why three outcomes beat two: stability and binary search both need to know when two elements are equal, and multi-key ordering falls out of a non-zero-then-fall-through chain.

for a senior

Demonstrate the contract discipline - antisymmetry, transitivity, determinism - and name the two comparators that break it in real code: the one that never returns zero, and the subtraction that overflows.

for a principal

Own the convention: one exported comparison function per ordered type, reused by sorting, sortedness checks and searching, so the ordering can never drift between the code that builds a sorted structure and the code that queries it.

## The signature ```go func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int) ``` The element type is `any` here - that is the whole point of the `Func` variants: they sort things Go has no built-in ordering for, such as structs, pointers or a type you want ordered on a field. You supply the ordering, as a function of two elements returning an `int`. Only the **sign** of that `int` is read: - **negative** - `a` sorts before `b` - **zero** - `a` and `b` are equal as far as this ordering is concerned - **positive** - `a` sorts after `b` `-1`, `-42` and `math.MinInt` are all equally "before". ## Why not a boolean less-than A boolean `less(a, b)` answers exactly one question: is `a` strictly before `b`? Everything else has to be derived from it. To find out whether two elements are *equal*, you have to evaluate `less(a, b)` and `less(b, a)` and observe that both are false - two calls and a piece of reasoning at every comparison site. The three-way `int` gives you all three outcomes from one call, and that matters for three concrete reasons. **Stability needs the tie.** `slices.SortStableFunc` promises that elements which compare equal keep their input order. It can only honour that if the comparison tells it which pairs *are* equal - a `cmp` that returns `-1` or `1` and never `0` reports no ties at all, so "stable" degenerates to meaningless. **Searching needs the tie even more.** `slices.BinarySearchFunc(x, target, cmp)` decides at each step whether to go left, go right, or stop - a genuinely three-way branch. With a boolean less-than there is no "stop": you cannot express found. The `int` contract is what lets the same mental model, and often literally the same function, cover `SortFunc`, `SortStableFunc`, `IsSortedFunc` and `BinarySearchFunc`. **It composes.** Multi-key ordering falls out naturally: compare on the first key, and if the result is non-zero return it; otherwise fall through to the next key. With booleans, the same logic needs nested calls in both directions. ```go slices.SortFunc(users, func(a, b user) int { if a.Age != b.Age { if a.Age < b.Age { return -1 } return 1 } return strings.Compare(a.Name, b.Name) }) ``` ## The obligations on your comparison function The function must define a consistent ordering over the elements. Concretely: - **Antisymmetric** - if `cmp(a, b)` is negative then `cmp(b, a)` must be positive. - **Transitive** - if `a` sorts before `b` and `b` before `c`, then `a` must sort before `c`. - **Deterministic** - the same pair must always give the same sign. A comparison that consults a mutable field, a clock, or a random source can make the sort produce nonsense; the package does not promise to detect that. Break any of these and the outcome is undefined - not a panic you can catch, just a wrong order. ## The two mistakes that actually get made **Never returning zero.** Code written by someone thinking in booleans looks like `if a.Age < b.Age { return -1 }; return 1`. That claims `b` sorts before `a` whenever their ages are equal, which is not antisymmetric: `cmp(a, b)` and `cmp(b, a)` both come back positive for a tie. The plain `SortFunc` will usually still produce something age-ordered, which is why the bug survives review - but a stable sort has no ties to preserve, and a binary search built on the same function will never report a match. **Subtracting.** `return a - b` on integers is the classic C-style comparator, and it silently overflows: with `a` a large positive and `b` a large negative value, the difference wraps to a negative number and the sign is inverted. Compare with explicit branches instead, or use `strings.Compare` for strings. ## Choosing between SortFunc and SortStableFunc `slices.SortFunc` is unstable and does no allocation for a scratch buffer; it is the default. Reach for `slices.SortStableFunc` when equal keys carry distinguishable payloads and the input order among them is meaningful - a log already ordered by timestamp that you now want grouped by level, where the timestamps must stay ascending inside each level. Stability costs extra work, so pay for it when the guarantee is being used, not by reflex.

  • What breaks if your comparison returns 1 for 'not less' and never returns 0?
    Equality becomes invisible. The function is no longer antisymmetric - both `cmp(a, b)` and `cmp(b, a)` are positive for a tied pair - so the ordering is undefined in principle. In practice `slices.SortFunc` often still looks right, `slices.SortStableFunc` has no ties to preserve, `slices.IsSortedFunc` can report a correctly sorted slice as unsorted, and `slices.BinarySearchFunc` never reports a match because it never sees zero.
  • When would you choose slices.SortStableFunc over slices.SortFunc?
    When elements compare equal on the sort key but carry payload you can tell apart, and their input order is meaningful. Re-sorting timestamp-ordered log lines by severity is the canonical case: within one severity you want the timestamps still ascending. Stability costs extra work, so use SortFunc by default and SortStableFunc when the guarantee is actually being relied on.
  • Why is `return a - b` a poor comparison for a slice of ints?
    It overflows. If `a` is near the maximum int and `b` is negative, the subtraction wraps around and the sign flips, so the comparison claims the larger value sorts first. The bug only shows on extreme inputs, which is exactly when it is hardest to spot. Write explicit branches on `<` and `>`, and return an explicit zero for the tie.
  • How do you express a two-key order - by age, then by name - with this contract?
    Compare the first key and return that result if it is non-zero; only fall through to the second key when the first ties. `if a.Age != b.Age { ... }` then `return strings.Compare(a.Name, b.Name)`. The three-way shape is what makes the fall-through natural: zero from the first key is precisely the signal that the tiebreaker should decide.

saying these in an interview costs you the question

  • Passes a boolean less-than function to slices.SortFunc
  • Never returns 0, so ties are never reported
  • Uses a - b as an integer comparison and ignores overflow
  • Assumes slices.SortFunc is stable
  • Thinks only -1, 0 and 1 are valid return values