Skip to content
Tutorials Center
My learning

Topics

Lesson 89 of 201 ยท Collections

Sorting with Comparable and Comparator

Learn to sort in Java - the compareTo contract, Comparable natural order, Comparator.comparing, thenComparing, reversed, nullsFirst, List.sort and stable sorting.

Sorting numbers is easy: everybody agrees that 3 comes before 7. Sorting a list of employees is not. By name? By salary, highest first? By department, and then by name inside each department? Java can't guess, so you tell it, in one of two ways:

  • Comparable: the class itself defines its one natural order. String, Integer, LocalDate and every enum already do.
  • Comparator: a separate object that defines an order. You can have as many as you like, and you can build them in a single readable line.

Everything that sorts or keeps things sorted in Java, including List.sort, Arrays.sort, TreeMap, TreeSet, PriorityQueue, Collections.max and Stream.sorted, relies on these two interfaces. This lesson shows how to write them, how to combine them, and the bugs that make sorting quietly wrong.

How comparison works

Both interfaces boil down to a method that compares two values and returns an int:

Result Meaning
negative the first value comes before the second
zero they're equal for sorting purposes
positive the first value comes after the second

Only the sign matters. -1 and -500 mean the same thing, so never test for == -1; test for < 0.

Java Natural ordering of built-in types

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Notice the exact numbers: "apple".compareTo("banana") happens to return the difference between the first differing characters. Don't rely on that; the contract only promises the sign.

String's natural order compares UTF-16 code units, so all uppercase letters sort before lowercase ones, and accented letters land after z. For human-friendly, language-aware sorting use a Collator (Comparing and Converting Strings).

Comparable: the natural order of your class

Implement Comparable<T> when your type has one obvious order that everyone would expect: version numbers, money amounts, dates, sizes. You write compareTo, and from then on your objects work in TreeSet, Collections.sort and friends without any extra arguments.

Java Versions that sort like versions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Sorted as text, "1.10.0" lands before "1.2.9" because the character '1' is less than '2'. With a proper compareTo, each part is compared as a number. (Comparator can express the same logic more compactly, as you'll see below; a compareTo can simply delegate to a static final Comparator field.)

The compareTo contract

For sorting to work, compareTo must behave consistently. For any a, b and c:

  1. Sign flips: a.compareTo(b) and b.compareTo(a) have opposite signs (or are both 0).
  2. Transitive: if a > b and b > c, then a > c.
  3. Equal stays equal: if a.compareTo(b) == 0, then a and b compare the same way against every other value.
  4. Strongly recommended: a.compareTo(b) == 0 exactly when a.equals(b). This is called being consistent with equals.

Break rules 1 to 3 and the result of sorting is undefined: elements come out in the wrong order, and List.sort may even throw IllegalArgumentException: Comparison method violates its general contract! when it detects the inconsistency. Break rule 4 and sorted sets and maps behave differently from hash-based ones, which TreeMap and TreeSet demonstrates. BigDecimal is the famous example in the JDK: 1.0 and 1.00 are not equals, but compareTo returns 0, so a HashSet keeps both and a TreeSet keeps one.

The subtraction trap

You'll find this "clever" comparison in old code and interview questions:

Java Why return a - b is broken

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

2,000,000,000 - (-2,000,000,000) is 4 billion, which doesn't fit in an int and wraps around to a negative number (see Working with Numbers). The comparator then claims the big number is smaller: the "sorted" list comes out as [2000000000, -2000000000], and Collections.max picks -2,000,000,000 as the largest value. Always use Integer.compare, Long.compare, Double.compare, or the Comparator factory methods below.

Comparator: orders on demand

A Comparator<T> is a functional interface with one method, compare(a, b). You can write it as a lambda, but you rarely need to: the static and default methods on Comparator build almost any order from small pieces.

Method Builds
Comparator.comparing(keyFn) order by a Comparable key, e.g. comparing(Person::name)
comparingInt, comparingLong, comparingDouble order by a primitive key, with no boxing
comparing(keyFn, keyComparator) order by a key, using a specific comparator for the key
.thenComparing(...) tie-breaker used when the previous comparison gives 0
.reversed() the opposite order of everything before it
Comparator.naturalOrder(), reverseOrder() natural order and its reverse
Comparator.nullsFirst(c), nullsLast(c) wraps c so null values sort first or last instead of crashing
Java Sorting employees five different ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Read a comparator chain left to right as a sentence: "compare by department, then by salary reversed". Each thenComparing is consulted only when everything before it says "equal".

Where reversed() applies

reversed() reverses the whole comparator it's called on, including any thenComparing before it. Compare these two:

Java
// department Z to A, AND names Z to A within each department
Comparator.comparing(Employee::dept).thenComparing(Employee::name).reversed()

// department A to Z, salary high to low within each department
Comparator.comparing(Employee::dept)
          .thenComparing(Comparator.comparingInt(Employee::salary).reversed())

To reverse only one key, reverse that key's comparator and pass it to thenComparing, as in the fourth sort of the example. For a single reversed key there's also a shortcut: thenComparing(Employee::name, Comparator.reverseOrder()).

The lambda-and-reversed compile error

Method references and lambdas behave differently when you chain reversed():

Java
staff.sort(Comparator.comparing(Employee::name).reversed());       // compiles
staff.sort(Comparator.comparing(e -> e.name()).reversed());         // error!
staff.sort(Comparator.comparing((Employee e) -> e.name()).reversed()); // compiles

In the middle line the compiler has to infer the type of e from comparing(...) alone, before it sees .reversed() and staff.sort. It can't, so e becomes Object, and Object has no name() method: "cannot find symbol". A method reference, an explicitly typed lambda parameter, or a type witness (Comparator.<Employee, String>comparing(...)) fixes it.

Handling null values

Comparators built with comparing throw NullPointerException when they meet a null key. Wrap the key comparator with nullsFirst or nullsLast to decide where missing values go:

Java Sorting with missing values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The first sort fails on purpose. The second puts tasks without a due day at the end and sorts those by title. To handle a null element (rather than a null field), wrap the whole comparator: Comparator.nullsFirst(myComparator).

Sorting methods and stability

Call Sorts
list.sort(comparator) a List in place; null means natural order
Collections.sort(list) / Collections.sort(list, comparator) same as list.sort (older style)
Arrays.sort(array) / Arrays.sort(array, comparator) an array in place; comparators only work with object arrays, not int[]
stream.sorted() / stream.sorted(comparator) a new sorted stream, original untouched
Collections.max(c, comparator), stream.max(comparator) the largest element, without sorting

Sorting objects with List.sort or Arrays.sort is stable: elements that compare as equal keep their original relative order. (Java uses TimSort for objects, which is stable and very fast on data that's already partly sorted. Primitive arrays use a dual-pivot quicksort, where stability doesn't matter because equal numbers are indistinguishable.)

Stability means you can sort in several passes, and earlier orders survive as tie-breakers:

Java Stable sorting keeps earlier order for ties

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Within each year, the songs are still in title order from the first pass. In new code, a single comparingInt(Song::year).thenComparing(Song::title) says the same thing more clearly, but stability is why multi-pass sorting (like clicking column headers in a table UI) behaves the way users expect.

Sorting is O(n log n). If you only need the smallest or largest element, use Collections.min/max or stream().max(...), which are O(n); if you need the top few, use a heap as shown in Queues, Deques and PriorityQueue.

Comparable or Comparator?

  • Implement Comparable when there is one natural order that nobody would argue with, and make it consistent with equals.
  • Use Comparator for every other order, for orders that depend on context (a table sorted by whichever column the user clicked), and for classes you can't modify.
  • Don't make a class Comparable just to sort it once. A Comparator at the call site is clearer.
  • Store reusable comparators as constants: static final Comparator<Employee> BY_SALARY_DESC = ...;.

Sorting maps by value is a common need with a ready-made answer: Map.Entry.comparingByValue() and comparingByKey(), which you'll use with streams in Collecting Stream Results.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does "b".compareTo("a") > 0 evaluate to, and what does a positive result mean?

    A positive result means the first value sorts after the second. Only the sign of the result is meaningful.
  2. 2. Why is (a, b) -> a - b a bad comparator for int values?

    For values far apart, such as 2,000,000,000 and -2,000,000,000, the difference overflows int and flips sign. Use Integer.compare.
  3. 3. Which comparator sorts by department A to Z and, within a department, by salary from highest to lowest?

    reversed() reverses everything before it, so only the salary comparator should be reversed before it is passed to thenComparing.
  4. 4. A list is sorted by name, then sorted again with list.sort(comparingInt(Person::age)). Two people have the same age. In what order do they appear?

    List.sort is stable, so elements that compare as equal keep their relative order from before the sort, which was name order.
  5. 5. Why does Comparator.comparing(e -> e.name()).reversed() fail to compile when sorting a List<Employee>?

    With reversed() chained on, the compiler cannot use the sort call's target type to infer the lambda parameter. Use Employee::name or (Employee e) -> e.name().

Summary

  • Comparisons return an int whose sign says before (negative), equal (zero) or after (positive).
  • Comparable.compareTo defines a class's single natural order; keep it consistent with equals and obey the contract (sign flips, transitivity).
  • Never compare by subtraction; use Integer.compare and friends.
  • Build comparators with comparing, comparingInt, thenComparing, reversed, naturalOrder, reverseOrder and nullsFirst/nullsLast; reversed() applies to the whole chain before it.
  • List.sort, Collections.sort and Arrays.sort on objects are stable, so equal elements keep their earlier order.
  • Use Comparable for an obvious natural order and Comparator for everything else.

Next: Immutable Collections and Utility Methods, where you'll create read-only lists, sets and maps and meet the handy helpers in the Collections class.