The labs on this site need JavaScript to run. The same content is written out below.

Learn › Java › Collections

Sorting and Comparator

Who decides the sort order, and why is comparing by subtraction wrong?

Sorting means asking "which of these two comes first?" over and over. The class can define the answer itself (Comparable), or the answer can be supplied from outside at the time of sorting (Comparator).

Checked against real execution · Checked by running 16 combinations on JDK 21

Concepts in this lab

Comparable and Comparator

These are the two ways to define the order of objects. Comparable is an interface that a class implements itself, and its single method, compareTo, defines the natural ordering of that class. A Comparator is a way of comparing that is created separately, outside the class, and it lets you sort the same objects by a different sort key each time. Both return a negative number if the first object comes first, 0 if the order cannot be decided, and a positive number if it comes later. Returning the difference of two numbers as it is can flip the sign through overflow, so use Integer.compare or Comparator.comparingInt.

Stable sort

This is a sort that keeps the original order of elements whose comparison result is equal (0), even after sorting. For example, if a list that is in order by name is sorted by score with a stable sort, people with the same score are still in order by name. The documentation states that List.sort, Collections.sort, and Arrays.sort for object arrays, which sort objects in Java, are stable. So you can rely on it when you sort by several sort keys one after another, or when you sort a list shown on the screen in which the order of equal values must not change.

Integer overflow

This is what happens when the result of a calculation goes beyond the range that its type can hold and becomes an unexpected value. A Java int can hold -2147483648 through 2147483647, and a result beyond this range crosses over to the opposite end of the range and continues from there, with no exception. For example, adding 1 to 2147483647 gives -2147483648. No error occurs and the wrong value is silently used, so the problem is hard to find. For a calculation that can go out of range, use long, or use a method such as Math.addExact, which throws an exception when the result overflows.

Method reference

This is a syntax that refers to an existing method by name in place of a lambda. You write it by joining a class (or an object) and a method name with ::, as in String::length or System.out::println. It is a shorter way to write a lambda that does nothing but call one method.

Lambda expression

This is a syntax, introduced in Java 8, for writing a function with no name in a compact way. It has the form (parameters) -> body, and it is used as the implementation of a functional interface, which has only one abstract method. It lets you pass behavior (code) to another method as if it were a value.

Try these

• Default settings — Large numbers are given to a Comparator that compares by subtraction. A wrong order comes out with no exception.
• The same code with small numbers — The list is sorted correctly. That is why the problem does not show up in tests.
• Fixed with comparingInt — The list is sorted correctly even with large numbers.
• The order that Comparable defines — The list is sorted by name, as the compareTo of the class says. The balances are not looked at.
• People with the same balance — Even when the list is sorted by balance, accounts with the same balance keep their original order.
• By name when equal — thenComparing supplies a second sort key.
• Sorting in reverse — Largest balance first. Accounts with the same balance still keep their original order.

Running with the default settings

1. List<Account> list = new ArrayList<>(List.of(...)): Five accounts are stored in the order park, choi, kim, lee, han. park and kim have the same balance, 2 billion, and choi and lee have the same balance, -2 billion.
2. Comparator<Account> order = (a, b) -> a.balance() - b.balance(): This uses the difference of the two balances as the result of the comparison. The code was written on the assumption that the result is negative when a is smaller, 0 when the two are equal, and positive when a is larger.
3. order.compare(park, choi): 2000000000 - (-2000000000) is computed. Mathematically it is 4000000000, but an int can hold only -2147483648 through 2147483647, so the result is out of range (overflow). The value that actually comes out is -294967296. It is negative, so park goes before choi. This answer is wrong: it says that park, which has the larger balance, comes first.
4. order.compare(park, kim): The two balances are equal, so the result is 0. Zero means that the order of the two cannot be decided, and the sort does not reorder such a pair.
5. list.sort(order): The sort calls order.compare many times to decide the positions. The sorted order is park(2 billion), kim(2 billion), choi(-2 billion), lee(-2 billion), han(0). The accounts should run from the smallest balance, but they do not. That is because the comparison gave a wrong answer.
6. System.out.println(list): Prints the sorted list. No exception was thrown. The wrong order came out without any warning.

Result of this run

• Comparing by subtraction flips the sign when the difference of the two numbers is outside the int range (about -2.1 billion to 2.1 billion). A wrong order can come out silently without any exception, and in some cases an IllegalArgumentException is thrown. Integer.compare(a, b) and Comparator.comparingInt compare the two numbers without subtracting, so they are safe.

Code

record Account(String owner, int balance) implements Comparable<Account> {
    @Override
    public int compareTo(Account other) {        // the order the class defines itself: by name
        return owner.compareTo(other.owner);
    }
}

List<Account> list = new ArrayList<>(List.of(
    new Account("park", 2_000_000_000), new Account("choi", -2_000_000_000),
    new Account("kim", 2_000_000_000), new Account("lee", -2_000_000_000),
    new Account("han", 0)));

Comparator<Account> order = (a, b) -> a.balance() - b.balance();   // compares by subtraction
System.out.println(order.compare(list.get(0), list.get(1)));   // park and choi
System.out.println(order.compare(list.get(0), list.get(2)));   // park and kim

list.sort(order);
System.out.println(list);

Assumptions of this model

The sorted result, the values returned by the two calls to compare, and whether the balance order is correct were checked for all 16 combinations against the result of running the same code on JDK 21 on this PC. Of the value that compare returns, the specification defines only the sign (negative, zero, or positive). Specific numbers such as the 1 and -1 of comparingInt and the 13 and 5 of the string comparison are the values that came out on JDK 21. When you supply a comparison that breaks the rules, such as a Comparator that compares by subtraction, the sorted result depends on the internal behavior of the sorting algorithm. The wrong order in this lab is the result that List.sort on JDK 21 produces with five elements. The documentation of List.sort says that an IllegalArgumentException may be thrown if the comparator is found to violate the Comparator contract (this case was not run). The sort makes many comparisons, but the screen shows only two of them, run separately.

Previous lab: Removing during iteration · Next lab: Lambda expressions and functional interfaces