PHASE 9Intermediate ~27 min· topic 10 of 13

Topic 9.10

Comparable and Comparator

In one line

Comparable gives a class one built-in natural order (compareTo), and a Comparator is a separate object that describes any other order. Sorting, TreeMap, TreeSet, PriorityQueue, min and max all work through one of the two.

Think of it like this

A class lines up for the school photo. The teacher has a usual rule: shortest at the front. That's the class's natural order, built into how the class lines up every time (Comparable). For the sports-day photo the coach brings a card that says "line up by house colour, then by age". The card is a separate rule you can hand to anyone who's arranging a line (Comparator). The children didn't change; only the rule used to compare them did.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Natural order: The one default way a type sorts itself, defined by its compareTo method.
Comparable: An interface a class implements to give itself a natural order, with the method compareTo.
Comparator: A separate object (often a lambda) that compares two values, so you can sort in any order you like.
compareTo / compare: Methods that return negative, zero or positive to say whether the first value comes before, ties with, or comes after the second.
Stable sort: A sort that keeps equal elements in the order they had before sorting.
Key extractor: A function that pulls out the value to sort by, like Person::age.
Overflow: When an int calculation goes past the biggest int and wraps around to a negative number (Topic 1.3).
Consistent with equals: compareTo returns 0 exactly when equals returns true. Sorted sets and maps rely on it.

Step by step

01Negative, zero, positive: the only thing that matters

Every comparison answers one question: does a come before b (negative), are they tied (zero), or does a come after (positive)? "apple".compareTo("banana") is negative because a comes before b. Integer.compare(7, 3) is positive.

Code must only test the sign: if (x.compareTo(y) < 0). Never == -1. String.compareTo returns the difference of the first differing characters, so "a".compareTo("c") is -2, not -1.

Main.javawhole filejava

System.out.println("apple".compareTo("banana"));   // -1  (a before b)
System.out.println("a".compareTo("c"));              // -2  (only the sign matters!)
System.out.println(Integer.compare(7, 3));           //  1
System.out.println("Zoo".compareTo("apple"));        // -7  ('Z' is 90, 'a' is 97: capitals sort first)

02Give a class its natural order with Comparable

Implement Comparable<Student> and write compareTo. Now Collections.sort, TreeSet, Collections.min/max and PriorityQueue all understand students without extra code.

Compare fields with the library helpers: Integer.compare, Long.compare, Double.compare, String.compareTo, Boolean.compare. They return the right sign and never overflow.

Main.javawhole filejava

record Student(String name, int marks) implements Comparable<Student> {
    public int compareTo(Student other) {
        return Integer.compare(this.marks, other.marks);   // fewer marks first
    }
}

03Many orders with Comparator

The same students might be sorted by name on one screen and by marks (highest first) on another. A class gets only one compareTo, so the other orders are comparators, built where they're needed.

list.sort(cmp) (Java 8) sorts in place using a comparator; list.sort(null) means natural order. Collections.sort(list, cmp) does the same thing in older code.

Main.javawhole filejava

students.sort(Comparator.comparing(Student::name));                 // A to Z
students.sort(Comparator.comparingInt(Student::marks).reversed());  // highest marks first

04Chaining: thenComparing for ties

comparing(Person::city).thenComparing(Person::age, Comparator.reverseOrder()).thenComparing(Person::name) means: sort by city; if cities tie, by age with the oldest first; if that ties too, by name.

Internally each step is a comparator that calls the previous one and only consults the next key when the result is 0. You could write the same logic by hand with if (c != 0) return c; lines, but the chained form is harder to get wrong.

Chaining: thenComparing for tiesdiagram

Rendering diagram…

05Why a - b is a bug

(a, b) -> a - b looks fine for small numbers. But Integer.MAX_VALUE - (-10) overflows to a large negative number, so the comparator claims the biggest int is smaller than -10. The sort then produces a wrong order (and on bigger lists may throw "Comparison method violates its general contract!").

The fix is boring and always correct: Integer.compare(a, b) or Comparator.comparingInt(...). The same trap exists with (int) (x.price() - y.price()) for doubles: small differences round to 0 and break ties. Use Double.compare.

06How TreeSet uses compareTo instead of equals

A TreeSet or TreeMap never calls equals or hashCode. To decide "is this already here?" it walks the red-black tree (Topic 9.6) calling compare, and a result of 0 means "same element".

So a comparator that only looks at length treats "pear" and "plum" as the same element: new TreeSet<>(Comparator.comparing(String::length)) keeps only one of them. Make sure a comparator used for sets and maps breaks ties all the way down (add .thenComparing(Comparator.naturalOrder())).

07Nulls and reversed orders

Comparator.naturalOrder() throws NullPointerException on a null. Wrap it: Comparator.nullsFirst(Comparator.naturalOrder()) puts nulls at the front, nullsLast(...) at the back.

.reversed() flips a whole comparator. Watch out with chains: comparing(A).thenComparing(B).reversed() reverses both keys. To reverse only one key, pass Comparator.reverseOrder() (or a reversed comparator) to that one thenComparing.

Try it yourself

1
Flip the natural order
In "Natural order with Comparable", change compareTo to return Integer.compare(other.marks, this.marks);. Predict the new first line before you press Run. (Highest marks first: Cara, Asha, Ben.)
2
Reverse only one key
In the Comparator example, remove Comparator.reverseOrder() so ages sort ascending inside each city, then add .reversed() at the very end of the chain instead. Run it: which keys flipped? (All of them: cities now go Pune before Delhi too.)
3
Watch the overflow happen
In "The a - b overflow trap", print Integer.MAX_VALUE - (-10) directly. You'll see -2147483639, the wrapped-around value that fooled the comparator.

Code & diagrams

Natural order with Comparable Java 16+ New tab

Records arrived in Java 16; the Comparable part works the same on any class since Java 1.2.

Expected output

[Student[name=Ben, marks=67], Student[name=Asha, marks=82], Student[name=Cara, marks=91]]
lowest: Ben
Ben vs Cara: -1

Comparator.comparing, thenComparing and reverseOrder Java 16+ New tab

Comparator.comparing and thenComparing are Java 8; the record needs Java 16.

Expected output

Delhi 28 Asha
Delhi 28 Dev
Pune 31 Ravi
Pune 25 Meera
youngest: Meera, oldest: Ravi

The a - b overflow trap New tab

With the broken comparator the sort didn't crash: it silently produced a wrong order. That's worse than an exception.

Expected output

bad says big < small?  true
good says big < small? false
sorted with bad:  [3, 5, 2147483647, -2147483648]
sorted with good: [-2147483648, 3, 5, 2147483647]

nullsFirst, case-insensitive order and reversed New tab

Natural String order is by character code, so the capital F in "Fig" sorts before every lowercase word.

Expected output

[null, null, Fig, apple, banana, pear]
[apple, banana, Fig, pear, null, null]
[banana, apple, pear, Fig]

Writing compare by hand (what thenComparing does for you)java

Comparator<Person> byCityThenAgeDescThenName = (a, b) -> {
    int c = a.city().compareTo(b.city());
    if (c != 0) return c;
    c = Integer.compare(b.age(), a.age());   // swapped: oldest first
    if (c != 0) return c;
    return a.name().compareTo(b.name());
};

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Sort objects that have no natural order

Remove implements Comparable<Student> and the compareTo method, but keep Collections.sort(list);.

terminal

$ javac Main.java

── what you'll see ──

Main.java:13: error: no suitable method found for sort(List<Student>)

Collections.sort(list);

method Collections.<T#1>sort(List<T#1>) is not applicable

(inference variable T#1 has incompatible bounds

equality constraints: Student

upper bounds: Comparable<? super T#1>)

method Collections.<T#2>sort(List<T#2>,Comparator<? super T#2>) is not applicable

(cannot infer type-variable(s) T#2

(actual and formal argument lists differ in length))

...

1 error

Break #2

A TreeSet that loses elements

Build new TreeSet<>(Comparator.comparing(String::length)) and add "pear", "plum" and "fig".

terminal

$ java Main.java

── what you'll see ──

[fig, pear]

Myth vs fact

Myth

compareTo returns -1, 0 or 1.

Fact

It returns any negative number, zero, or any positive number. String.compareTo often returns -2, 7 and so on. Always test the sign.

Myth

return a - b; is a neat compare for ints.

Fact

It overflows for large or negative values and silently mis-sorts. Use Integer.compare(a, b).

Myth

TreeSet uses equals to find duplicates.

Fact

Sorted sets and maps use only compare/compareTo. A result of 0 means duplicate, whatever equals says.

Myth

Sorting twice destroys the first order.

Fact

Java's object sort is stable, so sorting by name and then by city leaves names in order within each city.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Comparator.comparing boxes primitive keys. comparingInt, comparingLong and comparingDouble avoid that, which matters for large sorts: they call Integer.compare on raw ints.
▸
TimSort detects contract violations opportunistically during merges and throws IllegalArgumentException ("Comparison method violates its general contract!"). Small lists (under 32 elements) use binary insertion sort and never detect it, which is why a broken comparator can pass tests and fail in production on bigger data. (-Djava.util.Arrays.useLegacyMergeSort=true was the old escape hatch; fix the comparator instead.)
▸
BigDecimal.compareTo ignores scale (2.0 vs 2.00 is 0) while equals doesn't, so a HashSet<BigDecimal> and a TreeSet<BigDecimal> can disagree about the same data. Know which one you're using when money is involved.
▸
Comparators built with comparing(...) are serializable only if you ask for it ((Comparator<T> & Serializable)). Lambdas capturing state can also make a TreeMap hard to serialize. Prefer static final comparator constants for shared orders.

Remember this

1
**Comparable<T>** (in java.lang) has one method: int compareTo(T other). It returns a negative number when this comes before other, zero when they are equal in order, and a positive number when this comes after. Only the sign matters, never the size. String, Integer, LocalDate and most value types implement it, which is why Collections.sort(listOfStrings) just works.
2
**Comparator<T>** (in java.util) is the same idea as a separate object: int compare(T a, T b). You use one when a class has no natural order, when you need a different order (by length instead of alphabetically, newest first), or when you can't change the class. A comparator is a functional interface, so a lambda like (a, b) -> Integer.compare(a.age(), b.age()) is a comparator.
3
Since Java 8, Comparator has factory and combinator methods that read like English: Comparator.comparing(Person::city), .thenComparing(Person::name), .reversed(), Comparator.comparingInt(Person::age) (avoids boxing), Comparator.naturalOrder(), Comparator.reverseOrder(), Comparator.nullsFirst(...) and nullsLast(...). Building orders this way is shorter and avoids the classic bugs below.
4
The contract matters. A correct order must be consistent: sgn(compare(a,b)) == -sgn(compare(b,a)), transitive (a<b and b<c means a<c), and stable for equal elements. Break it and sorting can produce nonsense or throw IllegalArgumentException: Comparison method violates its general contract!. The most famous way to break it is return a - b;, which overflows for large or negative ints. Use Integer.compare(a, b) instead.
5
"Consistent with equals" is a separate rule: ideally compareTo returns 0 exactly when equals is true. Sorted collections (TreeSet, TreeMap) use only compareTo/compare to decide whether two elements are the same. If two different objects compare as 0, a TreeSet keeps just one of them. (BigDecimal is the famous exception: 2.0 and 2.00 are compareTo-equal but not equals.)
6
Java's object sort (List.sort, Arrays.sort on objects, Collections.sort) is TimSort: stable (equal elements keep their original order) and O(n log n). Stability is what makes "sort by name, then sort by city" give a list grouped by city with names sorted inside each city. Primitive arrays use a dual-pivot quicksort, which isn't stable and doesn't need to be (equal ints are indistinguishable).

Explain it without notes

When would you implement Comparable, and when would you write a Comparator instead?

Why is (a, b) -> a - b a dangerous comparator, and what should you use?

Explain what "consistent with equals" means and what goes wrong in a TreeSet when it isn't.

Why does it matter that Java's object sort is stable? Give a concrete example.

Practice

Sort a list of words by length, shortest first, and alphabetically among words of the same length.

Write a Version record (major, minor, patch) that implements Comparable so 1.10.0 sorts after 1.9.3.

Given a Map<String, Integer> of word counts, print the entries sorted by count descending, then by word.

Trade-offs

↔
Comparable is convenient but fixes one order forever; Comparators are flexible but must be passed around (keep shared ones as static final constants).
↔
Chained comparing(...) comparators are clear and safe; hand-written compare methods can be slightly faster in hot loops but are easier to get wrong.
↔
comparing with boxed keys is simplest; comparingInt/Long/Double avoid boxing for large or frequent sorts.

Done when you can

Done when you can explain the negative/zero/positive contract and why only the sign matters.
Done when you can give a class a natural order with Comparable and build other orders with Comparator.comparing and thenComparing.
Done when you never write a - b in a comparator and can explain the overflow.
Done when you can explain why TreeSet and TreeMap use compare instead of equals.
Done when you can sort with nulls and reverse just one key of a multi-key order.

Command Palette

Words you'll meet

Step by step

01Negative, zero, positive: the only thing that matters

02Give a class its natural order with Comparable

03Many orders with Comparator

04Chaining: thenComparing for ties

05Why a - b is a bug

06How TreeSet uses compareTo instead of equals

07Nulls and reversed orders

Try it yourself

Flip the natural order

Reverse only one key

Watch the overflow happen

Code & diagrams

Break it on purpose

Sort objects that have no natural order

A TreeSet that loses elements

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can