--- title: 'Comparison and Sorting' source: 'https://academia.sh/en/courses/java-standard-library/comparison-and-sorting' course: 'The Standard Library and Streams' language: en updated: '2026-08-17T18:09:42+00:00' license: 'CC BY-SA 4.0' --- # Comparison and Sorting Natural order sits in a type's own compareTo, the comparator in a separate object the caller gives from outside; the same data can be arranged in two separate orders. Stable sorting is List's own promise and comes out byte-for-byte identical across two separate list implementations. The caller's rule: a comparator inconsistent with equals collapses two separate elements into one in a sorted set, a non-transitive comparator silently sorts wrong on small input and falls by name on large enough input. The bounding measurement shows the same comparator loses no element in a list — what produces the flaw is not the comparator, it is the container that turns it into a uniqueness decision. The previous four lessons measured the promises a container gives its own element. Ordering asks a different question: who decides **which order** a container's elements will be given in? Sometimes the decision sits inside the type itself, sometimes it is a separate object in the caller's hand — and this lesson opens that distinction and measures where an externally given rule's own flaws land. The pattern the previous lesson showed continues here too: a rule can compile, can work correctly on most inputs, and still either silently produce the wrong result or fall by name on a particular input. Sorting's difference is that the rule now sits **outside** the container, in an object the caller writes — and that object's own internal consistency is a separate matter that has to be tested before the container's own behavior. ## Natural Order Is the Type's Promise, the Comparator Is the Caller's When a type implements `Comparable` and writes its own `compareTo`, this order is called **natural order** and is part of the type's own definition — it sits inside the class, it is compiled together with the class. A `Comparator` is not like this: it is a separate object the caller writes at the call site, without ever touching the class. - **CO21** — The same three records are sorted in two separate orders: once by the record's own `compareTo` (by name), once by a `Comparator` the caller gives (by length). The record class is the same in both. ```java // NaturalOrder.java — natural order sits inside the type, the comparator outside import java.util.*; public class NaturalOrder { record Item(String name, int length) implements Comparable { @Override public int compareTo(Item o) { return name.compareTo(o.name); } } public static void main(String[] args) { List list = new ArrayList<>(List.of( new Item("zulu", 4), new Item("delta", 5), new Item("alfa", 4))); List natural = new ArrayList<>(list); Collections.sort(natural); System.out.println("natural order (Item.compareTo, by name) : " + natural); List external = new ArrayList<>(list); external.sort(Comparator.comparingInt(Item::length)); System.out.println("externally given comparator (by length) : " + external); } } ``` ``` natural order (Item.compareTo, by name) : [Item[name=alfa, length=4], Item[name=delta, length=5], Item[name=zulu, length=4]] externally given comparator (by length) : [Item[name=zulu, length=4], Item[name=alfa, length=4], Item[name=delta, length=5]] ``` The same three records, the same `List`, the same `sort` call family — and two separate results. `Collections.sort(natural)` takes no ordering information at all, because `Item` itself has already given a promise by writing `compareTo`; where this promise is written is known and it is in a single place. `external.sort(...)` does exactly the opposite: without `Item` changing at all, the caller defines its own rule (`length`) right at the call site. Both sortings being valid shows that sorting has no **single correct answer** — what is valid is being explicit about which promise is being used. The importance of this distinction comes from `compareTo` being compiled together with the class: every piece of code holding an `Item` class sees the same natural order, because the promise is written once, in the class's own file. A `Comparator`, though, can be rewritten at every call site; the same `Item` list can be sorted by name in one place, by length in another, by a third field in a third place, and all three are equally valid. Natural order carries the claim "this type has a single canonical order"; a comparator makes no such claim, it only provides an order suited to that call's need. ## Stable Sorting: The Interface's Own Guarantee `List.sort` does not just produce an order — its documentation also states it will preserve the **relative order** of elements considered equal. Whether this promise really comes out the same across two separate implementations can be measured. - **CO22** — The same seven records, each with a key and a first-order number, are written to `ArrayList` and `LinkedList` in the same order. The key repeats; the first-order number is unique and is used to read which record came first after sorting. ```java // Stability.java — is stable sorting identical across two list implementations import java.util.*; public class Stability { record Entry(int key, int firstOrder) {} public static void main(String[] args) { List source = new ArrayList<>(); int[] keys = {3, 1, 3, 2, 1, 3, 2}; for (int i = 0; i < keys.length; i++) source.add(new Entry(keys[i], i)); List array = new ArrayList<>(source); List linked = new LinkedList<>(source); array.sort(Comparator.comparingInt(Entry::key)); linked.sort(Comparator.comparingInt(Entry::key)); System.out.println("after ArrayList : " + array); System.out.println("after LinkedList : " + linked); System.out.println("are the two results byte-for-byte identical : " + array.equals(linked)); } } ``` ``` after ArrayList : [Entry[key=1, firstOrder=1], Entry[key=1, firstOrder=4], Entry[key=2, firstOrder=3], Entry[key=2, firstOrder=6], Entry[key=3, firstOrder=0], Entry[key=3, firstOrder=2], Entry[key=3, firstOrder=5]] after LinkedList : [Entry[key=1, firstOrder=1], Entry[key=1, firstOrder=4], Entry[key=2, firstOrder=3], Entry[key=2, firstOrder=6], Entry[key=3, firstOrder=0], Entry[key=3, firstOrder=2], Entry[key=3, firstOrder=5]] are the two results byte-for-byte identical : true ``` Both arrays are sorted by key, and within every key group `firstOrder` is **increasing**: the two records with key `1` stand in the order `1, 4`, the three records with key `3` in the order `0, 2, 5` — none of them changed places. `ArrayList` is array-based, `LinkedList` is node-based; despite being two separate internal structures, the result is byte-for-byte identical. This is not something left to the implementation, like the "iteration order" measured in previous lessons: `List.sort` requires stability directly in its own contract, and both implementations keep this requirement exactly. Here, stable sorting is the interface's promise, not the chosen class's preference. This forms a sharp contrast with what was measured in the previous lesson: questions like iteration order and null-key acceptance were left to the implementation and diverged across the three families. Stability is not like that — the `List` interface's `sort` method definition binds every class that implements this method. A method's contract sometimes says "every implementation gives the same answer," sometimes it says "the implementation chooses"; both can sit side by side within the same interface, and which is which can be confirmed not only by reading the documentation but also by running multiple implementations. ## The Caller's Rule: When the Comparator Is Inconsistent with equals A `TreeSet` or `TreeMap` decides uniqueness not by `equals`, but by whether the given comparator returns `0`. What happens if the comparator considers two different elements equal? - **CO23** — Two records are **different** by `equals` (their names differ) but have the same length. The same two records are added to a `TreeSet` built on length and a `HashSet` that looks at names. ```java // Inconsistent.java — what a sorted set does when the comparator is inconsistent with equals import java.util.*; public class Inconsistent { record Item(String name, int length) {} public static void main(String[] args) { Item a = new Item("apple", 4); Item c = new Item("kiwi", 4); System.out.println("a.equals(c) : " + a.equals(c)); Set sortedSet = new TreeSet<>(Comparator.comparingInt(Item::length)); sortedSet.add(a); sortedSet.add(c); System.out.println("set sorted by length, size : " + sortedSet.size()); System.out.println("set contents : " + sortedSet); Set hashSet = new HashSet<>(); hashSet.add(a); hashSet.add(c); System.out.println("HashSet size (same two records) : " + hashSet.size()); } } ``` ``` a.equals(c) : false set sorted by length, size : 1 set contents : [Item[name=apple, length=4]] HashSet size (same two records) : 2 ``` `equals` finds the two records **different**; `HashSet` reflects this correctly, size `2`. `TreeSet`, though, never asks its key `equals` at all — it only calls the comparator, and because the lengths are equal, it gets `0`. `TreeSet`'s uniqueness rule says "if `compareTo`/`Comparator` returns `0`, it is the same element"; the second `add` call is therefore not counted as an insertion, it is treated as an attempt to **overwrite** the first element, and the size stays at `1`. The flaw is not visible at compile time, and no exception falls either — `kiwi` silently disappears. This comes from the same family as the "writing equals without writing hashCode" flaw measured in the previous lesson, but from a separate mechanism. There, what was missing was `hashCode`, and the result was the lookup **failing to find.** Here, no method is missing at all; both `equals` and `compareTo`/`Comparator` are fully written, but the two are **mutually inconsistent.** `TreeSet`'s and `TreeMap`'s own documentation explicitly demands this consistency: the comparator is expected to be "consistent with" `equals`, but this expectation is not a type constraint the compiler can check — it is only a sentence in a contract, and if the caller does not read it, no warning is given at all. ## A Non-Transitive Comparator: Silent on Small, Exception on Large A comparator's second obligation is **transitivity**: if `a` is less than `b` and `b` is less than `c`, then `a` must be less than `c` too. What happens if this does not hold? - **CO24** — The same numbers are split into three groups (by `% 3` remainder) and the comparator compares these three groups in a cyclic order: group 0 less than 1, group 1 less than 2, group 2 less than 0. This cycle breaks transitivity from the start. Random numbers produced with the same fixed seed are sorted at two separate sizes (`50` and `100`). ```java // FullMeasurement.java — a non-transitive comparator: silent on small input, exception on large import java.util.*; public class FullMeasurement { static int compare(int x, int y) { int tx = x % 3, ty = y % 3; if (tx == ty) return 0; if ((tx == 0 && ty == 1) || (tx == 1 && ty == 2) || (tx == 2 && ty == 0)) return -1; return 1; } static int violationCount(Integer[] array) { int count = 0; for (int i = 0; i < array.length; i++) for (int j = i + 1; j < array.length; j++) if (compare(array[i], array[j]) > 0) count++; return count; } static Integer[] randomArray(int n) { Integer[] array = new Integer[n]; Random r = new Random(42); for (int i = 0; i < n; i++) array[i] = r.nextInt(1_000_000); return array; } public static void main(String[] args) { Integer[] small = randomArray(50); Arrays.sort(small, FullMeasurement::compare); System.out.println("n=50 -> no exception, violation count=" + violationCount(small)); Integer[] large = randomArray(100); try { Arrays.sort(large, FullMeasurement::compare); System.out.println("n=100 -> no exception (not expected)"); } catch (IllegalArgumentException e) { System.out.println("n=100 -> " + e.getClass().getSimpleName()); } } } ``` ``` n=50 -> no exception, violation count=195 n=100 -> IllegalArgumentException ``` The fifty-element array sorts silently — no exception at all — but the result is wrong **even by the comparator's own rule**: there are `195` cases where a pair of elements violates the cyclic rule, meaning the array never settled into a consistent order at all, it only looks like it did. In the hundred-element array, though, the algorithm's internal merge steps **detect** that the order they assumed does not hold, and throw an exception by name: "comparison method violates its general contract." The threshold depends on the data and sits somewhere between `50` and `100` here; small arrays can finish without doing enough work to trigger the sorting algorithm's internal consistency check, large arrays run into that check. Non-transitivity extracts two separate costs: a **silent wrong result** at small scale, an **exception** at large scale. The difference between these two costs comes from the sorting algorithm's own internal structure. On small inputs, the sorting algorithm processes the data by splitting and merging less, and can finish without ever running into the comparator's cyclic contradiction; as the input grows, an internal assumption the algorithm holds while merging the intermediate pieces it produces itself (that the two pieces being merged are each internally consistently ordered) breaks because of the comparator's contradiction, and the algorithm catches this with its own check. This check is not a promise of the `Comparator` interface, it is an internal safety measure of the chosen sorting algorithm; another algorithm could have returned with the same data without ever throwing an exception, only with a wrong result. ## The Bounding Measurement: Not the Comparator, the Container's Use of It The previous two measurements might seem to show the comparator itself is flawed. What happens if the same length comparator is given this time only for **sorting**, to a `List` and not a `TreeSet`? - **CO25** — The same inconsistent comparator (the length comparator from `Inconsistent.java`) is this time used to sort a three-record list; two of the records have the same length but are different by `equals`. ```java // NotLostInList.java — the same comparator loses no element in a list import java.util.*; public class NotLostInList { record Item(String name, int length) {} public static void main(String[] args) { List list = new ArrayList<>(List.of( new Item("pear", 5), new Item("apple", 4), new Item("kiwi", 4))); list.sort(Comparator.comparingInt(Item::length)); System.out.println("sorted list size : " + list.size()); System.out.println("sorted list : " + list); } } ``` ``` sorted list size : 3 sorted list : [Item[name=apple, length=4], Item[name=kiwi, length=4], Item[name=pear, length=5]] ``` All three records are still there; `apple` and `kiwi`, having the same length, stand next to each other, but both stay in the list, and because of stability `apple` (which came first in the input) is written before `kiwi`. In the `TreeSet` measurement, `kiwi` disappeared; here it does not. The difference is not in the comparator, it is in **how the comparator is used**: `List.sort` only reads it as a sorting rule, and a return of `0` deletes no element at all, it only leaves two elements next to each other. `TreeSet` reads that same return of `0` as a **uniqueness decision.** The same object, the same method, the same return value — two separate containers count it as answering two separate questions. What produces the flaw is not the comparator itself, it is the container that uses it as a uniqueness decision. This last measurement ties together all the lesson's threads. Writing a comparator is not, on its own, a flaw; the flaw surfaces depending on which container's hand that comparator is in, answering which question. `List.sort` only asks it "which one should come first" and reads a return of `0` as "both can stand in the same place." `TreeSet` reads that same return of `0` as "only one of these can exist." A comparator is a single method and carries a single decision; what decides which question it will be counted as answering is the container the caller chooses. ## Summary - Natural order sits in a type's own `compareTo` and is part of the type's definition; a comparator is a separate object the caller writes at the call site, never touching the class. The same data can be sorted in two separate orders. - Stable sorting is `List.sort`'s own promise: it produces a byte-for-byte identical result in `ArrayList` and `LinkedList`, without disturbing the relative order of elements with equal keys. - The caller's rule: if a comparator is inconsistent with `equals`, two elements that return `0` in a sorted set collapse into a single element — the flaw arises with no exception at all, silently. - A non-transitive comparator silently produces a wrong order on small input, and on large enough input runs into the sorting algorithm's own consistency check and falls by name; the threshold depends on the data. - Bounding measurement: the same inconsistent comparator loses no element in a list. What produces the flaw is not the comparator itself, it is the container that reads its return value as a uniqueness decision. ## Next Step Everything measured in this batch showed that the ordering rule no longer sits inside the container, it sits in an object given from outside — both `Comparator` and a type implementing `Comparable` were small contracts written independently of the container itself. The next topic looks at that object itself: what do the library's single-method types (functional interfaces), including `Comparator`, promise, and when that promise is written as a lambda at the call site, which guarantee stays in place, which one disappears?