Comparable, Comparator and Sorting Contracts

Sorting is the part of the collections API where a small logical mistake produces an exception with a famously unhelpful message, thrown from deep inside the JDK, sometimes and not always. Understanding the contract is what turns that into a two-minute fix.

Which one, and when#

Comparable is for a genuinely natural order — a LocalDate by time, a version by precedence, an invoice by number. If you find yourself asking "sorted by what?", it should be a Comparator.

public record Employee(String name, String department, int salary, LocalDate hired)
        implements Comparable<Employee> {
 
    // Natural order: by name. Chosen because it is the order a human
    // reading a list of employees expects by default.
    @Override
    public int compareTo(Employee other) {
        return this.name.compareTo(other.name);
    }
}

The contract#

For all x, y, z, writing sgn for the sign of the result:

1. Antisymmetry — sgn(compare(x, y)) == -sgn(compare(y, x)).
2. Transitivity — if compare(x, y) > 0 and compare(y, z) > 0, then compare(x, z) > 0.
3. Consistency of equals — if compare(x, y) == 0, then compare(x, z) and compare(y, z) have the same sign for every z.
4. Recommended: compare(x, y) == 0 should agree with x.equals(y).

Rules 1–3 make a total order. A sort algorithm assumes one; give it something else and the result is not merely unsorted but arbitrary — or an exception.

// 1. Overflow. Fine for small values, wrong for large or mixed-sign ones.
Comparator<Integer> broken = (a, b) -> a - b;
broken.compare(Integer.MAX_VALUE, -1);   // overflows to a negative number
Comparator<Integer> fixed = Integer::compare;
 
// 2. Non-transitive tolerance. a~b and b~c but not a~c.
Comparator<Double> fuzzy = (a, b) -> Math.abs(a - b) < 0.5 ? 0 : Double.compare(a, b);
 
// 3. Mutable state. Another thread changes `priority` mid-sort and the
//    comparator gives different answers for the same pair.
Comparator<Task> unstable = Comparator.comparingInt(Task::priority);  // if priority is mutable

Building comparators#

Since Java 8 you almost never write compare by hand:

List<Employee> staff = new ArrayList<>(employees);
 
staff.sort(
    Comparator.comparing(Employee::department)                  // primary
              .thenComparing(Employee::salary, Comparator.reverseOrder())  // secondary, descending
              .thenComparing(Employee::name)                    // tie-break, deterministic
);
 
// Primitive specialisations avoid boxing every key:
staff.sort(Comparator.comparingInt(Employee::salary));
 
// Nulls, in either position:
staff.sort(Comparator.comparing(Employee::manager,
        Comparator.nullsFirst(Comparator.naturalOrder())));
 
// Reverse the whole chain, not just the last key:
staff.sort(Comparator.comparing(Employee::department)
                     .thenComparing(Employee::name)
                     .reversed());

Two things to say out loud in an interview. First, always end a chain with a unique tie-break — without one, equal elements come back in whatever order the input happened to have, and a paginated API that re-sorts on each request will show the same row on two pages. Second, .reversed() applies to everything before it, which is a common source of "the secondary sort is backwards".

Comparator.comparing extracts the key on every comparison, which is n log n extractions. If the key is expensive — a computed score, a parsed date — pre-compute it into a record and sort that, or use a decorate-sort-undecorate pass.

TreeMap, TreeSet and the equals divergence#

Sorted collections define membership by comparison, not by equals. This is a genuine behavioural difference and a favourite question:

Set<BigDecimal> hash = new HashSet<>(List.of(new BigDecimal("1.0"), new BigDecimal("1.00")));
Set<BigDecimal> tree = new TreeSet<>(List.of(new BigDecimal("1.0"), new BigDecimal("1.00")));
 
hash.size();   // 2 — equals() compares scale as well as value
tree.size();   // 1 — compareTo() ignores scale, so they are duplicates

Neither is wrong; they are answering different questions. But if you put objects into a TreeSet using a comparator that only looks at one field, every object sharing that field value collapses into one entry — silently discarding data. When a TreeSet "loses" elements, this is always why.

A TreeMap built with a comparator also uses it for get, containsKey and remove. A key that compares as 0 with a stored key will find it, even if the two are not equal.

Stability, and why it matters#

TimSort — a hybrid of merge sort and insertion sort, tuned for partially ordered real-world data — is stable: elements that compare equal keep their input order. That property is what makes multi-pass sorting valid:

staff.sort(Comparator.comparing(Employee::name));        // secondary key first
staff.sort(Comparator.comparing(Employee::department));  // primary key second
// Result: grouped by department, alphabetical within each — because pass two
// preserved the ordering established by pass one.

It also gives TimSort its performance profile: O(n) on already-sorted or reverse-sorted input, O(n log n) worst case, and much better than that on the "runs of sorted data" shape that database results and log files usually have.

Primitive arrays are sorted with a dual-pivot quicksort instead — not stable, but with no object identity there is nothing to observe. It is also why Arrays.sort(int[]) has an O(n²) worst case on adversarial input while Arrays.sort(Integer[]) does not.

Interview checklist#

Have crisp answers for: the difference between the two interfaces; why a - b is wrong; what "consistent with equals" means and the BigDecimal example; why sorting throws that contract exception; and why a paginated endpoint needs a tie-break column. The last one is the question that distinguishes someone who has shipped a sorted API from someone who has only sorted a list.