sorting and comparators

the picture

you know how you sort a spreadsheet by city, then by name, and expect names to stay sorted within each city? that only works because the sort is stable, and it only reads well in code because java lets you say it as one chain.

a comparator is a judge with one job: given two things, say which goes first (negative), second (positive), or "don't care" (zero). everything else, the sort does.

Comparable: the natural order

a class that has one obvious order implements Comparable<T> and its compareTo. String (alphabetical by char code), Integer, LocalDate, BigDecimal all do. that's what Collections.sort(list), TreeMap and TreeSet use when you don't pass anything.

record Player(String name, int score) implements Comparable<Player> {
    public int compareTo(Player o) {
        return Integer.compare(score, o.score);
    }
}
 
void main() {
    var ps = new ArrayList<>(List.of(new Player("ada", 30), new Player("bob", 10), new Player("cy", 20)));
    Collections.sort(ps);
    IO.println(ps.stream().map(Player::name).toList());
    ps.sort(Comparator.comparing(Player::name).reversed());
    IO.println(ps.stream().map(Player::name).toList());
}

[bob, cy, ada]
[cy, bob, ada]

the contract, in short: compareTo must be antisymmetric (if a < b then b > a), transitive (a < b and b < c means a < c), and should agree with equals (returns 0 exactly when equals is true). break the last one and hash-based and tree-based collections disagree about duplicates (the BigDecimal story in sets).

Comparator: every other order

java.util.Comparator has a set of static and default methods that compose like lego. you almost never write compare by hand anymore.

• comparing(keyExtractor): compare by a key's natural order. comparingInt / comparingLong / comparingDouble skip the boxing.
• comparing(key, keyComparator): compare by a key, with a custom order for that key.
• thenComparing(...): tie-breaker, only consulted when everything before it says 0.
• reversed(): flips the whole chain built so far. to reverse only one key, reverse its key comparator: comparing(Person::age, reverseOrder()).
• nullsFirst(cmp) / nullsLast(cmp): decide where nulls go, instead of throwing.
• naturalOrder() / reverseOrder(): the Comparable order and its opposite.

inside the sort: TimSort

List.sort, Collections.sort, Arrays.sort(Object[]) and stream().sorted() all end up in TimSort (named after Tim Peters, who wrote it for Python). its insight: real data is rarely random. it's often partly sorted, or sorted in chunks, or reversed. so instead of ignoring that order, TimSort hunts for it.

1. find a run: the longest stretch starting here that's ascending, or strictly descending (reversed in place, which keeps it stable since no equal elements swap).
2. extend short runs: if a run is shorter than minRun (16 to 32 for big arrays), binary insertion sort grows it, which is fast on tiny ranges.
3. push and keep the stack balanced: each run on the stack must be longer than the one above it, and longer than the two above it combined. whenever that breaks, merge. this keeps merges between runs of similar size, which is where merging is cheapest.
4. merge what's left at the end.

the real merge also "gallops": when one run keeps winning, it switches to exponential search and copies whole blocks at once. arrays under 32 elements skip all of it and just get one run plus binary insertion sort.

the result: O(n log n) worst case, O(n) on already-sorted or reversed input, and stable. the price: up to n/2 extra references of scratch space for merging.