skip to content

How do you build a multi-key, mixed-direction ordering using Comparator combinators, and what are the correctness pitfalls?

level: seniorimportance: should knowfreq 55%

answer

  1. comparing → thenComparing → (per-key) reverseOrder
  2. reversed() flips the WHOLE chain to its left
  3. nullsFirst / nullsLast guard null keys
  4. Never a-b for ints → overflow; use Integer.compare / comparingInt
  5. Inconsistent comparator → 'violates its general contract'

basics

~10 s

Chain Comparators: start with Comparator.comparing(key1), add .thenComparing(key2) for tie-breaks, and use .reversed() to flip a direction. Be careful where .reversed() applies and handle nulls explicitly so sorting doesn't throw.

solid answer

~40 s

Comparator exposes static factories and default combinators to assemble composite ordering strategies. Comparator.comparing(Person::lastName) builds the primary key; .thenComparing(Person::firstName) breaks ties; .thenComparingInt(Person::age) avoids boxing for primitives. Direction is controlled with reverseOrder()/naturalOrder() or by reversing a single key — but watch scope: cmp.reversed() flips the *entire* composite, whereas comparing(key, Comparator.reverseOrder()) flips only that one key. The common pitfalls are: (1) putting reversed() at the wrong level so it reverses more than intended; (2) NullPointerException when a key extractor returns null — fix with nullsFirst/nullsLast wrappers; (3) inconsistent comparators that violate the contract (must be transitive and antisymmetric), which can corrupt TimSort and throw 'Comparison method violates its general contract'; (4) using subtraction like a-b for ints, which overflows. Prefer Integer.compare / comparingInt. Build the strategy once, reuse it, and keep it stateless.

code

java · 10 lines
java
record Emp(String dept, int salary, String name, String manager) {}

Comparator<Emp> cmp =
    Comparator.comparing(Emp::dept)                            // dept asc
              .thenComparing(Emp::salary, Comparator.reverseOrder()) // salary desc (only this key)
              .thenComparing(Emp::name)                        // name asc
              .thenComparing(Emp::manager,
                  Comparator.nullsLast(Comparator.naturalOrder())); // null managers last

list.sort(cmp);

go deeper

for a junior

Can chain comparing and thenComparing for a two-key sort and use reversed() to flip order.

for a middle

Understands tie-break semantics of thenComparing, uses comparingInt to avoid boxing, and knows nullsFirst/nullsLast exist for null keys.

for a senior

Controls reversed() scope deliberately, avoids int-subtraction overflow, and can diagnose 'violates its general contract' as a broken total order.

for a principal

Reasons about the comparator contract formally (antisymmetry/transitivity), TimSort's contract checks, stability guarantees, and designs reusable stateless comparator strategies as part of an API surface.

## Goal Many real orderings are multi-key with mixed directions: 'by department ascending, then salary descending, then name ascending, nulls last'. `Comparator` lets you assemble such a composite **strategy** declaratively. This question is about doing that correctly. ## The building blocks **Static factories (entry points):** - `Comparator.comparing(keyExtractor)` — order by the value the extractor returns, using that value's natural ordering. - `Comparator.comparing(keyExtractor, keyComparator)` — order by the extracted value, but with an explicit comparator for *that key*. - `Comparator.comparingInt/Long/Double(keyExtractor)` — primitive-specialized, avoids autoboxing the key. - `Comparator.naturalOrder()` / `reverseOrder()` — the element's own `Comparable` ordering, forward/back. **Default (instance) combinators — each returns a NEW comparator:** - `.thenComparing(...)` — tie-breaker applied only when the prior comparator returns 0. - `.thenComparingInt/Long/Double(...)` — primitive tie-breakers. - `.reversed()` — reverses *the comparator it's called on*. - `Comparator.nullsFirst(cmp)` / `nullsLast(cmp)` — wrap a comparator to tolerate null elements/keys. ## Composing a multi-key strategy ```java Comparator<Emp> cmp = Comparator.comparing(Emp::department) // 1st key, ascending .thenComparing(Emp::salary, reverseOrder()) // 2nd key, descending .thenComparing(Emp::name); // 3rd key, ascending list.sort(cmp); ``` Each `thenComparing` only matters when all earlier keys tied — that's exactly the lexicographic, multi-key behavior you want. ## Pitfall 1 — where `.reversed()` applies (scope) `.reversed()` reverses the **whole comparator chain to its left**, not just the last key. These are different: ```java // WRONG if you only meant to reverse salary: Comparator.comparing(Emp::department) .thenComparing(Emp::salary) .reversed(); // reverses department AND salary // RIGHT — reverse only the salary key: Comparator.comparing(Emp::department) .thenComparing(Emp::salary, Comparator.reverseOrder()); ``` Reach for the per-key `comparing(key, reverseOrder())` form (or `Comparator.comparing(key).reversed()` *before* chaining) when you want a single key reversed. ## Pitfall 2 — nulls If a key extractor can return `null`, `comparing` will call `compareTo` on null → **NullPointerException** during sorting. Wrap with `nullsFirst`/`nullsLast`: ```java Comparator.comparing(Emp::manager, Comparator.nullsLast(Comparator.naturalOrder())); ``` ## Pitfall 3 — the comparator contract A comparator must impose a **total order consistent with itself**: - **Antisymmetry:** `sgn(compare(a,b)) == -sgn(compare(b,a))`. - **Transitivity:** if `a<b` and `b<c` then `a<c`. - Stable, deterministic results for equal inputs. If your custom logic violates this (e.g. ad-hoc rules that aren't transitive), the JDK's TimSort may detect the inconsistency and throw **`IllegalArgumentException: Comparison method violates its general contract!`**. Building from combinators over real `Comparable` keys keeps the contract automatically. ## Pitfall 4 — integer subtraction overflow A classic bug: ```java (a, b) -> a.age() - b.age() // overflows for large/negative values ``` If `a.age()` is very large and `b.age()` very negative, the subtraction overflows `int` and returns the wrong sign. Always use `Integer.compare(a.age(), b.age())` or `comparingInt(Emp::age)`. ## Pitfall 5 — stability The JDK sort is **stable**: equal elements keep their input order. If you rely on a prior sort as a tie-breaker (sort by secondary key, then by primary), stability preserves it — but it's clearer and safer to express all keys in one composite comparator. ## Reuse and statelessness A comparator should be **stateless** and is safe to build once and reuse (often a `static final` field). Don't capture mutable state in the lambda, and don't let `compare` have side effects. ## Summary Compose with `comparing(...).thenComparing(...)`, control direction per-key (mind `reversed()` scope), guard nulls with `nullsFirst/Last`, never subtract ints, and keep the contract total and consistent so TimSort doesn't reject it.

  • Why might sort throw 'Comparison method violates its general contract'?
    Because the comparator isn't a consistent total order — typically non-transitive or non-antisymmetric logic. TimSort detects the inconsistency mid-sort and throws IllegalArgumentException. Fix by composing from real Comparable keys.
  • How do you reverse only the second key in a two-key sort?
    Use the per-key form: comparing(key1).thenComparing(key2, Comparator.reverseOrder()). A trailing .reversed() would flip both keys.

saying these in an interview costs you the question

  • Calling .reversed() at the end expecting only the last key to flip
  • Using a-b subtraction for int keys (overflow)
  • Ignoring null keys, causing NPE mid-sort
  • Writing a non-transitive comparator and being surprised by IllegalArgumentException
  • Putting mutable state or side effects inside compare

context

resolving links…