Java Advanced Sorting

An order on the class, or an order at the call

Comparable is one method, compareTo, and implementing it says "this is how these objects line up when nobody passes a special rule." Comparator is compare, and the list can take a different one on every sort. Natural order belongs on the class when the domain has one. A report that wants name today and age tomorrow belongs in a comparator, so the class does not grow a second personality.

import java.util.Objects;

class Student implements Comparable<Student> {
    final String name;
    final int age;

    Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int compareTo(Student other) {
        return Integer.compare(age, other.age);
    }

    public boolean equals(Object other) {
        if (!(other instanceof Student)) {
            return false;
        }
        return age == ((Student) other).age && name.equals(((Student) other).name);
    }

    public int hashCode() {
        return Objects.hash(name, age);
    }
}

Read that pair carefully before you ship it. compareTo ties two students who share an age. equals still requires the name. They disagree, and a TreeSet<Student> will follow compareTo. The second twenty-year-old is a duplicate as far as the set is concerned, and equals would have kept both. Either compare by name and age, or define equals and hashCode on age alone, and mean it. The sorted collection will not paper over the split.

List<Student> students = new ArrayList<>();
students.add(new Student("Alice", 22));
students.add(new Student("Bob", 20));
students.add(new Student("Charlie", 25));

students.sort(Comparator.comparingInt(s -> s.age));
students.sort(Comparator.comparing(s -> s.name));

Comparator.comparing and comparingInt build the rule from a key. students.sort(null) uses natural order, the compareTo above. Arrays.sort sorts an array in place. Stream.sorted returns a new stream and leaves the source list alone. Arrays.parallelSort spends threads on large arrays, and the overhead is wasted on a short one.

A tie has to mean the same thing everywhere

BigDecimal documents the classic split. new BigDecimal("1.0") and new BigDecimal("1.00") have the same numeric value and different scales. compareTo returns 0. equals returns false. Put both into a HashSet and you have two elements. Put both into a TreeSet and you have one, because the tree asks the comparator, and the natural comparator says they are tied. If the scale is part of identity in your domain, a TreeSet<BigDecimal> is the wrong membership test. If the numeric value is identity, equals will surprise you instead. Pick the contract the collection will actually use.

The sign also has to be transitive and reversible: if a precedes b and b precedes c, then a precedes c, and comparing them in reverse flips the sign. Subtracting the keys, a - b, breaks the sign when the subtraction overflows. Integer.compare and comparingInt exist so the key can be the full int range.

students.sort(Comparator
    .comparing((Student s) -> s.name, Comparator.nullsLast(String::compareTo))
    .thenComparingInt(s -> s.age));

thenComparingInt is the second key, applied when the name comparison ties. nullsLast decides where a missing name sits, instead of throwing from compareTo on null. One comparator now states the whole order.

Timsort keeps the previous tie

Object sorts in the JDK go through a stable sort. Timsort merges runs and, when two elements compare equal, leaves them in the order it found them. Sort the students by age. Sort them again by name. Two students who share a name come out in age order, because the second sort was not allowed to reshuffle a tie. Primitive Arrays.sort does not make that promise. There is no separate identity to preserve once the values are bare ints.

The two-pass trick is how stability shows itself. When you already know both keys, thenComparing says them in one rule and you do not depend on the previous arrangement of the list. Stability still matters for a sort that is intentionally refining an order some earlier step established.