When writing a custom Comparator for sortedWith, what correctness contract must it satisfy, and what goes wrong if it doesn't? How do compareBy/thenBy help you stay correct?
answer
- Total order: sign-reversal + transitivity + equality consistency
- Broken comparator → 'violates its general contract' IAE
- Never (a - b) for Int/Double comparison — overflow/truncation
- Use compareTo / compareValues
- compareBy/thenBy compose valid orders for you
basics
~20 sA comparator must be consistent: if a comes before b and b before c, then a must come before c, and reversing the arguments must reverse the sign. If it isn't, sorting can give wrong or unstable results, or even throw. Using compareBy/thenBy avoids hand-written mistakes.
solid answer
~40 sComparators handed to sortedWith/sortWith must define a total order: reflexive (compare(a,a)==0 sign-wise), antisymmetric/sign-reversing (sign(compare(a,b)) == -sign(compare(b,a))), and transitive (a<=b and b<=c implies a<=c, and equality transitivity). The underlying TimSort assumes this. A broken comparator — e.g. comparing floats with subtraction that overflows, mixing inconsistent rules, or returning nonzero for truly-equal elements inconsistently — can produce wrong order, lose stability, or throw IllegalArgumentException: 'Comparison method violates its general contract!'. compareBy/thenBy build comparators by delegating to each key's own compareTo, which is already a valid total order, and compose them transitively, so you rarely violate the contract. For doubles, use compareValues or a.compareTo(b) rather than (a - b).toInt(). For nullables, nullsFirst/nullsLast keep totality.
code
kotlin · 8 lines// Broken: subtraction overflows and breaks transitivity
val bad = Comparator<Int> { a, b -> a - b }
// Sorting wide-ranging ints with `bad` can throw or mis-order.
// Correct, contract-safe approaches:
val safe1 = Comparator<Int> { a, b -> a.compareTo(b) }
val safe2 = compareBy<Int> { it } // delegates to Int.compareTo
listOf(Int.MAX_VALUE, Int.MIN_VALUE, 0).sortedWith(safe2) // [MIN, 0, MAX]go deeper
Knows a comparator returns negative/zero/positive and that compareBy is the easy way.
Avoids subtraction-based comparison and uses compareTo/compareBy, aware results can be wrong otherwise.
States the total-order contract, recognizes the TimSort 'violates its general contract' exception and its causes.
Designs and tests contract-correct comparators, prefers DSL composition, reasons about totality with nulls/NaN, and guards hot paths against subtle ordering bugs that only appear at scale.
## The comparator contract `sortedWith(comparator)` (and `sortWith`, `Collections.sort`) require the `Comparator<T>` to impose a **total order**. Concretely: 1. **Sign-reversal (antisymmetry):** `sign(compare(a, b)) == -sign(compare(b, a))` for all a, b. 2. **Transitivity:** if `compare(a, b) <= 0` and `compare(b, c) <= 0`, then `compare(a, c) <= 0`. 3. **Equality transitivity:** if `compare(a, b) == 0`, then for every c, `sign(compare(a, c)) == sign(compare(b, c))`. Kotlin sorting delegates to Java's `Arrays.sort`, which uses **TimSort** — and TimSort actively detects violations. ## What breaks - **The infamous exception:** an inconsistent comparator can trigger `java.lang.IllegalArgumentException: Comparison method violates its general contract!` mid-sort. This is not a rare theoretical issue; it surfaces on real data once the input is large/varied enough to expose the inconsistency. - **Silent wrong order / lost stability:** even when no exception fires, results may be subtly mis-ordered. ## Common ways to break it ```kotlin // BUG: subtraction can overflow and isn't valid for doubles Comparator<Int> { a, b -> a - b } // overflows for large/negative ints Comparator<Double> { a, b -> (a - b).toInt() } // truncates; ties become unequal ``` Use the safe forms instead: ```kotlin Comparator<Int> { a, b -> a.compareTo(b) } // correct Comparator<Double> { a, b -> compareValues(a, b) } // correct, handles NaN ordering ``` ## Why compareBy/thenBy are safer `compareBy { it.key }` delegates comparison to `key.compareTo`, which for stdlib `Comparable` types is already a valid total order. `thenBy` composes additional valid orders **lexicographically**, preserving transitivity and sign-reversal automatically. So building comparators from the DSL makes contract violations very unlikely: ```kotlin val cmp = compareBy<Item>({ it.priority }, { it.createdAt }) .thenBy { it.id } items.sortedWith(cmp) // contract-correct by construction ``` ## Nulls and totality A comparator that throws on null keys is not total over the actual element domain. `nullsFirst(inner)` / `nullsLast(inner)` extend a comparator to place nulls deterministically, keeping the order total. ## Practical guidance - Prefer the DSL (`compareBy`/`thenBy`/`nullsLast`) over hand-rolled `compare`. - Never subtract to compare numbers; use `compareTo`/`compareValues`. - If you must hand-write, unit-test antisymmetry and transitivity on representative data.
- Why is Comparator<Int> { a, b -> a - b } dangerous?Subtraction can overflow Int (e.g. MAX - MIN), flipping the sign and violating transitivity, which can mis-sort or throw the 'violates its general contract' exception.
- What exception signals a broken comparator and where does it come from?IllegalArgumentException 'Comparison method violates its general contract!', thrown by Java's TimSort when it detects inconsistent comparisons during the sort.
- How do compareBy/thenBy reduce the risk of contract violations?They delegate to each key's compareTo (an already-valid total order) and compose levels lexicographically, preserving transitivity and sign-reversal automatically.
saying these in an interview costs you the question
- Comparing numbers with subtraction (a - b)
- Not knowing a bad comparator can throw at runtime
- Returning arbitrary nonzero for 'equal' elements
- Ignoring null keys so the order isn't total
- Assuming any compare function is fine as long as it 'mostly' orders