Java 54: Sorting & Comparator Mechanics
easy⏱ 5 mincoursejava
The Comparator contract
compare(a, b) returns a negative int if a should come before b, zero if they're equal in this ordering, and positive if a should come after b. It must be a total order: consistent, transitive, and antisymmetric. A common bug is return a - b on ints — it overflows for large/negative values; prefer Integer.compare(a, b).
Comparator<Person> byAge = Comparator.comparingInt(Person::age);
Comparator<Person> byAgeThenName =
byAge.thenComparing(Person::name);
list.sort(byAgeThenName); // stable multi-key sort
list.sort(byAge.reversed()); // descending by age
Stability and why it composes
A stable sort never reorders elements the comparator calls equal. This is why you can sort by a secondary key first, then a primary key, and get correct tie-breaking — or simply chain thenComparing. Insertion sort and TimSort are stable; a naive quicksort is not, which is why Arrays.sort uses dual-pivot quicksort only for primitives (where stability is irrelevant) and TimSort for objects.
Stable insertion sort with a Comparator
Write insertionSort(arr, cmp) that sorts in place by shifting larger elements right and inserting each element into its slot — using cmp(a, b) for every comparison. Count comparisons and shifts. Sort [5, 2, 9, 1, 5, 6] ascending and print the result and the counters. Then sort an array of {name, score} by score and confirm two equal scores keep input order (stability).
Build comparators, don't write compare()
Prefer the factory + combinator API: Comparator.comparing(keyExtractor), .thenComparing(...), .reversed(), Comparator.nullsFirst(...). It reads top-to-bottom in priority order and avoids hand-rolled if ladders. Reach for a hand-written compare only for genuinely custom ordering logic.
Quiz: why not a - b for an int comparator?
(a, b) -> a - b looks fine but overflows: if a = Integer.MAX_VALUE and b = -1, the subtraction wraps to a negative number, inverting the order. Always use Integer.compare(a, b) (or Comparator.comparingInt), which is overflow-safe.