Sorting with Comparator

Sorting is daily work — reports, leaderboards, anything shown to a person in an order they expect. Java gives you two mechanisms, and one of them has a trap that produces a wrong order with no exception at all.

Comparable: one natural order

A class implements Comparable<T> to declare the way it sorts:

record Tiffins(int count) implements Comparable<Tiffins> {
    @Override
    public int compareTo(Tiffins other) {
        return Integer.compare(count, other.count);
    }
}

compareTo returns a negative number if this comes first, zero if they tie, positive if other comes first. String, all the number wrappers, LocalDate and enums are all Comparable already.

Use it when there is one obvious order. A subscriber has no obvious order — by name? by tiffins? by pincode? — so it should not implement Comparable at all.

Comparator: any order you like

List<Sub> subs = new ArrayList<>(List.of(
        new Sub("Priya", "411207", 26),
        new Sub("Arjun", "411014", 26),
        new Sub("Kavita", "411207", 30),
        new Sub("Amit", "411014", 18)));

subs.sort(Comparator.comparing(Sub::name));

[Amit(18), Arjun(26), Kavita(30), Priya(26)]

Comparator.comparing(Sub::name) reads as "compare by name". The Sub::name is a method reference — module 6's subject — and it is worth using here now because the alternative is four lines of anonymous class for something that is one idea.

The building blocks

They chain:

subs.sort(Comparator.comparingInt(Sub::tiffins).reversed());

[Kavita(30), Arjun(26), Priya(26), Amit(18)]

subs.sort(Comparator.comparing(Sub::pincode).thenComparing(Sub::name));

[Amit(18), Arjun(26), Kavita(30), Priya(26)]

subs.sort(Comparator.comparingInt(Sub::tiffins).reversed().thenComparing(Sub::name));

[Kavita(30), Arjun(26), Priya(26), Amit(18)]

Note that last one carefully. Arjun before Priya — both on 26, tie broken by name ascending. .reversed() applies to everything before it, not to the whole chain, so the tie-break stays ascending. To reverse both you would call .reversed() at the very end, and to reverse only the tie-break you write .thenComparing(Comparator.comparing(Sub::name).reversed()).

Getting this wrong produces a report sorted almost right, which nobody notices until a customer does.

The trap: subtraction

The comparator people write from memory:

list.sort((a, b) -> a - b);

It works for small numbers and lies for large ones:

List<Integer> nums = List.of(2_000_000_000, -2_000_000_000, 0);

a - b          : [2000000000, -2000000000, 0]
naturalOrder   : [-2000000000, 0, 2000000000]
comparingInt   : [-2000000000, 0, 2000000000]

The first list is not sorted at all, and nothing threw. The reason is the overflow from module 2:

2_000_000_000 - (-2_000_000_000) = -294967296

A negative result means "already in order", so the sort leaves the largest number first. Never subtract in a comparator. Use Integer.compare(a, b), Comparator.comparingInt(...) or naturalOrder() — all of which handle the full range.

The same applies to long, and to any comparator built by hand. If you find yourself writing return x - y;, replace it with Integer.compare(x, y) on sight.

A second hand-written comparator bug worth knowing: (a, b) -> a < b ? -1 : 1 never returns zero, so it claims every element is greater than itself. Sorting may produce an unstable order, and TreeSet and TreeMap built on it behave unpredictably. A comparator must return 0 for equal elements.

Nulls

List<String> withNull = new ArrayList<>(Arrays.asList("Priya", null, "Arjun"));
withNull.sort(Comparator.naturalOrder());

NullPointerException

withNull.sort(Comparator.nullsFirst(Comparator.naturalOrder()));

[null, Arjun, Priya]

nullsFirst and nullsLast wrap any comparator. They are the right answer when nulls are genuinely possible — and a sign worth heeding that the data probably should not contain them.

Sorting in place, or not

list.sort(comparator);                                    // modifies the list
List<Sub> copy = list.stream().sorted(comparator).toList(); // leaves it alone

copy    : [Amit(18), Arjun(26), Kavita(30), Priya(26)]
original: [Kavita(30), Arjun(26), Priya(26), Amit(18)]

Collections.sort(list) and Arrays.sort(array) are the older in-place forms. list.sort(...) is the modern one.

Java's sort is stable: elements that compare equal keep their relative order. That is why chained tie-breaks work, and it also means you can sort by one field and then by another to get the same result as a combined comparator — though saying it once with thenComparing is clearer.

TreeSet and TreeMap use the comparator, not equals

This one loses data.

Set<Sub> byTiffinsOnly = new TreeSet<>(Comparator.comparingInt(Sub::tiffins));
byTiffinsOnly.addAll(subs);
System.out.println(byTiffinsOnly.size() + " from " + subs.size());

TreeSet size 3 from 4 subscribers
contents: [Amit(18), Arjun(26), Kavita(30)]

Priya is gone. She and Arjun both took 26 tiffins, the comparator says they compare equal, and a sorted set treats "compares equal" as "the same element". equals was never consulted.

The equals-and-hashCode lesson's contract has a partner here: a comparator used for a sorted collection should be consistent with equals — it should return zero only for elements that are genuinely equal. Add a tie-break:

new TreeSet<>(Comparator.comparingInt(Sub::tiffins).thenComparing(Sub::name));

Now all four survive, ordered by tiffins with names breaking ties.

Check your work

When should a class implement Comparable? When there is one obvious natural order. A subscriber has several plausible orders, so it should not.

What does compareTo return? Negative if this comes first, zero for a tie, positive if the other does.

What does .reversed() apply to? Everything built before it in the chain, not the whole chain. A thenComparing added afterwards stays ascending.

Why is (a, b) -> a - b wrong? Subtraction overflows. 2_000_000_000 - (-2_000_000_000) is negative, so the sort concludes the larger number comes first — and nothing throws. Use Integer.compare.

What is wrong with (a, b) -> a < b ? -1 : 1? It never returns zero, so it claims every element is greater than itself. Sorted collections built on it misbehave.

How do you sort a list containing nulls? Wrap the comparator in Comparator.nullsFirst(...) or nullsLast(...).

Why did the TreeSet lose an element? A sorted set treats "compares equal" as "the same element" and never calls equals. Two subscribers with the same tiffin count collapsed into one. Add a tie-break so the comparator is consistent with equality.

Which sort leaves the original alone? stream().sorted(...).toList(). list.sort(...) sorts in place.

Practice 3, the four orders. By name: [Amit, Arjun, Kavita, Priya]. By tiffins descending: [Kavita(30), Arjun(26), Priya(26), Amit(18)]. By pincode then name: [Amit, Arjun, Kavita, Priya] — 411014 before 411207. By tiffins descending then name: [Kavita(30), Arjun(26), Priya(26), Amit(18)], with Arjun before Priya because the tie-break stayed ascending.

Practice 5, the TreeSet loss. With comparingInt(Sub::tiffins) the set holds 3 of 4 and Priya vanishes silently. Adding .thenComparing(Sub::name) restores her. The general rule: a comparator for a sorted collection must return zero only for elements you consider genuinely the same, or the collection quietly deduplicates things that are not duplicates.

Practice

1. Implement Comparable. Give a small record a natural order and sort a list of them with Collections.sort. Then decide whether a Subscriber should implement it, and write one sentence of justification.

2. Break it with subtraction. Sort [2000000000, -2000000000, 0] with (a, b) -> a - b and then with Comparator.naturalOrder(). Print both. Then print the subtraction itself.

3. Build four comparators. By name; by tiffins descending; by pincode then name; by tiffins descending then name. Predict each output before running.

4. Find the .reversed() boundary. Write comparingInt(Sub::tiffins).reversed().thenComparing(Sub::name) and then comparingInt(Sub::tiffins).thenComparing(Sub::name).reversed() and explain the difference in the tie-break.

5. Lose data in a TreeSet. Build one with a comparator on a non-unique field, add four subscribers, and print the size. Then add a tie-break and confirm all four survive.

6. Harder — a league table. Sort subscribers by tiffins descending, then by name ascending, and print with a rank column where ties share a rank (1, 2, 2, 4). Then add a customer whose name is null and make the sort survive it. Then decide whether allowing a null name was ever a good idea, and where the right place to stop it would have been — the answer is module 3's constructor validation.

Next: choosing the right collection, with the measurements behind each choice.