The Comparator Interface

Imagine a program that builds a list of words, asks Java to put them in order, and then prints the list. Sorting looks like a single step, but it touches several parts of the language at once: the list, the items inside it, and a utility method that does the work. This article approaches the topic from the outside in. You will first see what happens when a list is sorted, then learn which rules govern the order, and finally learn how to change that order with a Comparator.

As you read, keep one question in mind: when the sorted output is not what you expected, where in the chain of steps did the result diverge? Learning to answer that question is the real skill this article builds.

A natural first guess is that the List interface would provide a sort method, since sorting a list seems like a basic operation. It does not. The likely reason is that sorting only makes sense for certain kinds of objects, so the designers of the interface left it out. Instead, the sorting methods are static methods of a separate class, java.util.Collections.

Sorting a list is therefore a call on the Collections class rather than a method you invoke on the list itself. You pass the list in as an argument. If you have used the Arrays class to sort arrays, the idea is similar: a helper class supplies the operation, and you supply the data.

The simplest form of the call takes one argument, the list. Its job is to sort the list into ascending order. Here is that form applied to the three words from the opening prediction.

Trace what changed. Before the call, the list held the items in insertion order. After the call, the same list object holds them in ascending order. The printed output reflects that change, because the list was rearranged in place rather than copied into a new list.

The phrase ascending order means the smallest item comes first and the largest comes last, using the natural ordering of the items. For this call to work, the items in the list must implement the Comparable interface. The source material gives two families of examples where this holds: Strings, and the wrapper classes such as Integer and Double. Those types already know how to compare themselves, so Collections.sort() can rely on that knowledge.

Sometimes the natural ordering is not the one you want, or the items do not implement Comparable at all. For those cases there is a second form of the call that takes a Comparator as its second argument. When a comparator is supplied, Collections.sort() uses it to compare items in the list, instead of relying on the items' own natural ordering. The comparator is a separate object, so the ordering rule lives outside the items. This is what makes the second form useful for custom orders.

Notice the division of responsibility. The list is still the thing being rearranged. The items are still the things being compared. What changes is the source of the rule that decides which of two items belongs earlier.

Consider a list of words that should be ordered by how many characters each word has, rather than alphabetically. A Comparator can express that rule. The example below is an original illustration written for this article, not taken from the source. It defines a comparator whose compare() method compares the lengths of two Strings.

Read the compare() method as the rule. It receives two words and returns a number. A negative result means the first word belongs earlier, a positive result means it belongs later, and zero means the two are treated as equal for ordering. Here the rule says that a shorter word comes before a longer one. Collections.sort() calls this rule on pairs of items from the list, so the rule, not the items' natural ordering, decides the final arrangement.

The diagram below traces the calls during a two-argument sort. The caller hands the list and the comparator to Collections.sort(). Collections repeatedly asks the comparator to compare pairs of items taken from the list, reads the sign of each returned value, and rearranges the list accordingly. The comparator never touches the list directly; it only answers questions about two items at a time.

The sequence repeats: Collections picks pairs, the comparator returns a sign, and the list is rearranged, until the sort is finished. This is why the comparator's compare() method is the single place where the custom order is decided. Changing that method changes every placement the sort makes.

The choice between the two forms follows one question: does the ordering come from the items, or from a rule you supply? The flowchart below shows the decision path. With one argument the ordering comes from the items, which must implement Comparable. With a second argument the ordering comes from the Comparator object that Collections.sort() is given. In both cases the list is the thing being rearranged.

The names Comparable and Comparator are easy to confuse. The table below separates them by where the ordering logic lives and how each is supplied to sort().

When a sort produces an unexpected order, you can work backward through the questions this article has raised. Work through three checkpoints in order. First, identify which form of the call was used: the single-argument form or the two-argument form with a comparator. Second, if the single-argument form was used, check whether the items implement Comparable. Third, if a comparator was used, check what its compare() method returns for pairs of items. The divergence usually appears at one of these three checkpoints, because each one controls a different part of the ordering.