Comparable, Comparator and sorting

A music app lists your playlist by title, and one tap later by artist, or by length with the longest song first. Java can sort strings and numbers straight away, because they come with an order built in. A Song class you write has no order until you give it one, and Java refuses to sort it. This lesson shows how to give a class its own order, how to sort by any rule you choose, and how to keep data sorted while you add to it.

A list Java cannot sort#

Start with what already works. Here is a list of song titles and a list of song lengths in seconds, each sorted with one call to Collections.sort.

It prints [Gravity, Hello, Low Tide, Paper Boats] and [198, 214, 231, 245]: the titles in alphabetical order and the lengths from shortest to longest. Collections.sort rearranges the list you hand it. It does not make a new list.

Now put whole songs in the list, each with a title, an artist and a length, and sort that.

The message is long, but you have seen its shape before. Collections has two sort methods. The one you called takes only a list, and its type parameter has a bound: the elements must be Comparable<? super T>, a type that can compare itself with others of its kind. The list holds Song, which is not comparable, so the two demands clash, just as they did when max refused a list of songs in generics. The other sort needs a second argument, which you will meet later on this page.

Behind the message is a plain problem. Java cannot tell whether one song comes before another. It could go by title, by artist or by length, and nothing in Song says which.

A TreeSet finds out while running#

A TreeSet keeps its elements sorted all the time, so it needs the same rule. This program compiles. Run it.

It prints Adding the first song and then stops with a ClassCastException, whose message reads:

class Song cannot be cast to class java.lang.Comparable (Song is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')

The part in brackets only says where each class was loaded from, and can read a little differently on your computer. The start is what matters: to find the song's place, the set tried to treat it as a Comparable, and a Song is not one. It fails on the very first song, before there is anything to compare it with. Every TreeSet keeps its elements in a TreeMap, and a TreeMap compares its first key with itself, just to check that the key can be compared at all.

The two mistakes surface at different times because of how each one is declared. Collections.sort asks for a comparable type in its declaration, so the compiler can check the call. A TreeSet cannot ask for that in its type, because you may also give it a separate object that does the comparing (that comes later in this lesson), so it checks each element as it arrives.

Key idea

To sort anything, Java needs a rule that says which of two objects comes first. Strings and numbers bring their own. For a class of yours, you supply the rule.

Comparable: a natural order for your class#

The first way to supply the rule is to build it into the class. An order that a class carries with it is called its natural order: alphabetical for strings, smallest first for numbers. A class gets one by implementing Comparable<T>, the interface from java.lang that you saw in generics. Its single method, int compareTo(T other), compares the object it is called on with other.

Here Song gets an order by title. Its compareTo hands the work to the compareTo that String already has. Step through it and keep an eye on the call stack.

Now Collections.sort compiles, and the program prints Gravity by The Lanterns, Hello by Mira Sol and Paper Boats by June Okafor. In the trace, the sort calls your compareTo again and again, each time with two songs, and moves the songs according to the answers. compareToonly ever compares two songs. Deciding where each song ends up is the sort's job.

implements Comparable<Song>goes after the record's components, the way it would go after a class name. The <Song> says what a song can be compared with: other songs, so compareTo takes a Song and needs no cast.

What compareTo returns#

a.compareTo(b) returns an int, and only its sign carries meaning:

• A negative number means a comes before b.
• Zero means they tie: neither comes first.
• A positive number means a comes after b.

It prints -9, 9 and 0. gravity.compareTo(boats) is negative, so Gravity comes first. The 9 comes from String: the first letters differ, and 'G' (71) minus 'P' (80) is -9. Swap the two songs and the sign flips. A song compared with itself gives 0. Another class may answer -1 where String answers -9, so code that reads the result should only test the sign, with < 0, == 0 or > 0.

Sorting methods and TreeSet trust your compareTo to behave like a real order. The documentation of Comparable spells out what that means. For any objects a, b and c:

Comparing numbers: subtract, or Integer.compare?#

To order songs by length, compareTo must compare two int fields. A shortcut turns up in a lot of code: return the difference, seconds - other.seconds. When this song is the shorter one the difference is negative, when it is longer the difference is positive, and equal lengths give 0. Song lengths are small, so for them it works. For large numbers it can give the wrong sign.

A bank keeps each balance in cents as an int, and its Account record sorts with the subtraction shortcut. Zara has 2,000,000,000 cents, which is twenty million dollars. Omar owes money, so his balance is -500,000,000.

The first two lines both print -1794967296. The true difference is 2,500,000,000, but an int only goes up to 2,147,483,647. The subtraction runs past the top and wraps around, the way the hash codes did in HashMap and HashSet: Java subtracts 2³² (4,294,967,296) and lands on -1,794,967,296. compareToreturns that negative number, which claims that Zara comes before Omar. So the “smallest first” sort prints Zara 2000000000 above Omar -500000000, the richest account first, with no error anywhere.

Integer.compare(x, y) compares without subtracting. It returns a negative number when x is smaller, 0 when the two are equal and a positive number when x is larger, and nothing can overflow. Change that one line:

Now zara.compareTo(omar) prints 1, and the sort puts Omar first and Zara second. (The documentation only promises the sign. The JDK's code happens to return exactly -1, 0 or 1.)

Key idea

compareTo answers with a sign: negative when this object comes first, zero for a tie, positive when it comes after. Compare int fields with Integer.compare, never by subtracting.

When compareTo and equals disagree#

Two different songs can share a title. Mira Sol and Static Bloom have each released a song called Hello. With Song ordered by title alone, decide what each line prints, then run it.

It prints false, 0, 1 and 2. The two records are not equal, because their artists differ. compareTo still returns 0, because it only looks at titles. The HashSet asks hashCode and equals, sees two different songs and keeps both. The TreeSet never calls equals. To place the second Hello it compares it with what it already holds, gets 0 from the first Hello, and concludes the song is already there. Its add returns false, and Static Bloom's song is gone without any warning.

The documentation calls an order consistent with equals when compareTo returns 0 for exactly the pairs that equals calls equal. Song's order is not. A TreeSet or TreeMap built on such an order still works, but it no longer behaves like the sets and maps you know: it can drop elements, or report that it contains one it never received.

Comparing more than one field#

The fix is to look at a second field when the first one ties. Compare the titles and keep that answer unless it is 0. Only a tie moves on to the artists.

The set keeps all three songs and walks them in order: Gravity by The Lanterns, Hello by Mira Sol, Hello by Static Bloom. Step through the second add: the titles tie, so byTitle is 0, and the artists decide. If your app could hold two recordings of one song by one artist, compare the length as a third field, so that compareTo ties only when equals would say the records are equal.

Key idea

A TreeSet or TreeMap decides whether two elements are the same with compareTo, never with equals. Make compareTo return 0 only for objects that equals calls equal.

Now write one for an ordinary class. Version numbers are a good test, because sorting them as text goes wrong.

1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4 
5public class Main {
6    public static void main(String[] args) {
7        List<String> asText = new ArrayList<>(List.of("1.10", "1.9", "2.0", "1.2"));
8        Collections.sort(asText);
9        System.out.println("As text:     " + asText);
10 
11        List<Version> versions = new ArrayList<>();
12        versions.add(new Version(1, 10));
13        versions.add(new Version(1, 9));
14        versions.add(new Version(2, 0));
15        versions.add(new Version(1, 2));
16        Collections.sort(versions);
17        System.out.println("As versions: " + versions);
18    }
19}
20 
21class Version implements Comparable<Version> {
22    private final int major;
23    private final int minor;
24 
25    Version(int major, int minor) {
26        this.major = major;
27        this.minor = minor;
28    }
29 
30    @Override
31    public int compareTo(Version other) {
32        // TODO: compare major first. When the majors tie, compare minor.
33        return 0;
34    }
35 
36    @Override
37    public String toString() {
38        return major + "." + minor;
39    }
40}

Comparator: an order from outside the class#

A class has one natural order, but a music app needs several: by title, by artist, by length, longest first. And some classes cannot take a compareTo from you at all. String already has its alphabetical order, and you cannot open String and change it to sort words by length. For every order other than the natural one, Java uses a separate object called a comparator.

A comparator implements java.util.Comparator<T>, whose one abstract method is int compare(T a, T b). It answers with the same signs as compareTo, but both objects come in as arguments: negative when a comes first, zero for a tie, positive when a comes after b. With exactly one abstract method, Comparator is a functional interface, as enums and lambdas mentioned.

A comparator class#

The long way is a class that implements the interface. ByLength orders songs from shortest to longest:

playlist.sort(new ByLength()) sorts the list with that comparator, so the songs print from 198 seconds up to 245. This Song does not implement Comparable at all; the comparator supplies the whole rule. The last sort uses new ByLength().reversed(). reversed() is a default method of Comparator that returns a new comparator with the opposite order, so the longest song comes first and the program ends with Longest: Hello.

A lambda#

A whole class for one line of logic is a lot of ceremony. Since Comparator is a functional interface, a lambda can be its compare method:

The lambda takes two songs, a and b, and returns exactly what ByLength.compare returned.

Comparator.comparing and method references#

Most comparators look like that lambda: take the same value out of both objects, then compare the two values. That value is called the sort key. Comparator.comparing writes the rest for you. You give it a function that takes one song and returns its key, and it builds the comparator. These two lines both sort by artist:

The second line uses a method reference. In enums and lambdas you met Math::max, which names a static method. Song::artist names an instance method of Song and means “call artist() on whichever song you are given”. It is short for the lambda song -> song.artist(), and it reads almost like the sentence “compare songs by artist”. For an ordinary class with getters, name the getter the same way, as in Comparator.comparing(Student::getName).

For an int key, use Comparator.comparingInt(Song::seconds). Comparator.comparing(Song::seconds) works too, but it first boxes every length into an Integer, while comparingInt compares the plain int values. comparingLong and comparingDouble do the same for long and double keys. All of these arrived in Java 8, together with lambdas.

By artist, the order is [Paper Boats, Hello, Gravity], because June Okafor comes before Mira Sol and The Lanterns. By length it is [Gravity, Paper Boats, Hello]. The last line sorts strings by String::length, an order String itself does not have: [fig, kiwi, apple, banana].

Chaining comparators#

Real orders often need more than one key. Comparator has methods that build a bigger comparator out of smaller ones. Each returns a new comparator and leaves the one you called it on unchanged.

thenComparing breaks ties#

Sorting by artist leaves the songs of each artist tied. Comparator.comparing(Song::artist).thenComparing(Song::title) compares the artists first and uses that answer unless it is 0. Only for a tie does it compare the titles. That is the pattern you wrote by hand in compareTo: the first key decides unless it ties.

It prints June Okafor's two songs, then Mira Sol's two, then The Lanterns' one, and inside each artist the titles are alphabetical: Northern Lights before Paper Boats, Hello before Low Tide.

For an int key there is thenComparingInt, as in Comparator.comparing(Song::artist).thenComparingInt(Song::seconds), which puts each artist's shortest song first. thenComparing also accepts a whole comparator, and since a comparator is an object like any other, you can give the pieces names and reuse them: Comparator<Song> byArtist = Comparator.comparing(Song::artist); and a byTitle made the same way combine into byArtist.thenComparing(byTitle), the same order as above.

reversed flips everything before it#

reversed() returns a comparator that gives the opposite answer to the whole comparator it was called on. In a chain, that means everything written to its left. So where you put it decides which keys run backwards. Here the named byArtist and byTitle go into two chains that differ only in the place of reversed().

Both lines start with Gravity, because both put the artists from Z to A and The Lanterns comes last in the alphabet. They differ inside each artist. In the first chain reversed() comes after thenComparing(byTitle), so it flips the titles as well: Low Tide before Hello, Paper Boats before Northern Lights. In the second, reversed() only covers byArtist, and the titles added after it stay A to Z.

To flip just one key, flip it before it joins the chain. Both of these sort artists A to Z and, inside each artist, put the longest song first:

The second form passes a comparator for the key itself: thenComparing(Song::seconds, ...) takes the lengths and compares them with Comparator.reverseOrder(), which you meet properly below.

Build your own chains in the lab. Each button adds one call to the comparator, and the playlist sorts with List.sort after every click. The #column is each song's place in the original playlist.

Try artist, then title, then reversed(), and compare it with artist, reversed(), then title. Then sort by length alone and look at the two songs of 3:34: whichever comparator you build, tied songs keep their playlist order. The section on stable sorting explains why.

naturalOrder and reverseOrder#

Comparator.naturalOrder() is a comparator that calls compareTo, and Comparator.reverseOrder()is one that calls it the other way round. They let you use a type's natural order wherever a comparator is expected. words.sort(Comparator.reverseOrder()) sorts strings from Z to A, and both turn up as arguments to other comparators, as in the next program.

Lists with nulls in them#

Some songs are singles, released on no album, so their album is null. Sorting a list that contains null by its natural order throws a NullPointerException, because there is no object to call compareTo on. Comparator.nullsFirst(c) wraps another comparator c: every null comes first, and c orders the rest. nullsLast puts the nulls at the end.

It prints [null, null, Amber, Echoes, Tides], then [Tides, Echoes, Amber, null, null], and the plain Collections.sort on the last lines stops with a NullPointerException. To sort songs by an album that may be missing, pass the null-friendly comparator for the key: Comparator.comparing(Song::album, Comparator.nullsFirst(Comparator.naturalOrder())).

1import java.util.ArrayList;
2import java.util.Comparator;
3import java.util.List;
4 
5public class Main {
6    public static void main(String[] args) {
7        List<Player> players = new ArrayList<>();
8        players.add(new Player("Ravi", 120));
9        players.add(new Player("Ada", 95));
10        players.add(new Player("Mei", 120));
11        players.add(new Player("Leo", 140));
12        players.add(new Player("Bea", 95));
13 
14        // TODO: highest score first; players on the same score in alphabetical order
15        Comparator<Player> ranking = Comparator.comparing(Player::name);
16 
17        players.sort(ranking);
18        for (Player p : players) {
19            System.out.println(p.score() + " " + p.name());
20        }
21    }
22}
23 
24record Player(String name, int score) { }

Key idea

Build an order from small parts: comparing picks the first key, thenComparing breaks ties, and reversed() flips everything written before it.

List.sort, Collections.sort and stable sorting#

You have now sorted lists two ways. list.sort(comparator) is a method of List itself, added in Java 8. Collections.sort(list) sorts by the natural order, and Collections.sort(list, comparator) takes a comparator; both hand the work to list.sort, so the results are identical. Passing null to list.sortmeans “use the natural order”.

All of them sort the list in place and return nothing. That means the list must allow changes. A list made with List.of does not, so copy it into an ArrayList first:

The copy sorts to [Amber, Echoes, Tides] and then to [Tides, Echoes, Amber], while the original still prints [Tides, Amber, Echoes]. Sorting the List.of list itself throws an UnsupportedOperationException, even though nothing has been added or removed.

What stable means#

When a comparator says two elements tie, the documentation of List.sort decides which one goes first: the sort must not reorder equal elements. A sort that always keeps tied elements in the order they started in is called stable.

Here is a play queue, in the order the songs were added, sorted by artist alone. Step through it and watch the two songs of each artist.

The artists come out A to Z, and inside each artist the songs keep their queue order: Paper Boats before Northern Lights, Low Tide before Hello. Neither pair is alphabetical; they tie on artist, so the sort left them as they were. A stable sort lets you sort in two passes. Sort by title first, then by artist, and the artists come out in order with each artist's titles still alphabetical, the same result as byArtist.thenComparing(byTitle).

Sorting arrays of objects#

Arrays have the same two choices. Arrays.sort(array) sorts by the natural order, and Arrays.sort(array, comparator) by any comparator. The sort for arrays of objects is stable too.