Comparison and Sorting

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.

// 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<Item> {
        @Override public int compareTo(Item o) { return name.compareTo(o.name); }
    }

    public static void main(String[] args) {
        List<Item> list = new ArrayList<>(List.of(
                new Item("zulu", 4), new Item("delta", 5), new Item("alfa", 4)));

        List<Item> natural = new ArrayList<>(list);
        Collections.sort(natural);
        System.out.println("natural order (Item.compareTo, by name)          : " + natural);

        List<Item> 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.

// 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<Entry> 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<Entry> array = new ArrayList<>(source);
        List<Entry> 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.

// 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<Item> 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<Item> 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).

// 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.

// 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<Item> 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?