Multi-key sorting

Written Explanation

Why ties need a second key

Sort these players by score, highest first:

Mona:90  Zed:90  Ali:70  Bob:90  Cy:70

With only the score key, Mona, Zed, and Bob tie at 90. List sorting is stable (lesson 2), so tied players keep the order they had before. That is predictable for one run but meaningless: change the input order and the output changes. Real output from my test:

[Mona:90, Zed:90, Bob:90, Ali:70, Cy:70]

Bob should come before Mona if the tie-break is "name, A to Z".

thenComparing

thenComparing is a method on any Comparator. It returns a new comparator that first uses the original one, and if the result is zero, asks the second:

Comparator<Player> byRank =
        Comparator.comparingInt(Player::getScore).reversed()
                  .thenComparing(Player::getName);

Read it left to right: score first, highest at the front; if two scores tie, name A to Z. You can chain as many thenComparing calls as there are keys.

The overloads you will use:

Where reversed() applies

reversed() flips the whole comparator it is called on, not just the last key. Compare:

// score descending, THEN name ascending:
Comparator.comparingInt(Player::getScore).reversed()
          .thenComparing(Player::getName);

// the whole chain reversed (score descending AND name descending):
Comparator.comparingInt(Player::getScore)
          .thenComparing(Player::getName).reversed();

In the first form, reversed() is called when the comparator contains only the score key, so only the score is flipped. In the second form it is called after thenComparing, so the combined order is flipped: score descending and name descending (Z to A). Real results on the five players above:

first form:   [Bob:90, Mona:90, Zed:90, Ali:70, Cy:70]
second form:  [Zed:90, Mona:90, Bob:90, Cy:70, Ali:70]

The rule: reversed() flips everything before it. To reverse just one later key, give that key its own comparator, for example thenComparing(Player::getName, Comparator.reverseOrder()).

Choosing how a single key is compared

Sometimes the natural order of a key is not what the screen needs: names that should ignore capitals, or text that should be compared by length first.

thenComparing(key, keyComparator) and comparing(key, keyComparator) take a comparator for the key itself. This is how you ask for a case-insensitive name tie-break:

.thenComparing(Player::getName, String.CASE_INSENSITIVE_ORDER)

Ties in sorted sets and maps

TreeSet and TreeMap keep an element only if the comparator separates it from every element already in the set. After the full comparator byRank, two players survive as separate elements unless they have the same score and the same name. If your data can contain two different people with the same name and score, they collapse into one entry.

The remedy is to end the chain with a key that is unique, such as an id:

.thenComparing(Player::getName)
.thenComparingInt(Player::getId)

The Java documentation puts the general rule like this: the ordering should be consistent with equals, meaning that the comparator returns zero exactly when equals is true. In a list you can sort without a perfect tie-break. In a TreeSet, the ordering is the identity of the element.

Top N

Once a list is sorted, the best N are the first N. subList(0, n) takes the first n elements, where the end index is exclusive. The documentation says a sublist is a view of the original list, not a copy. If the list may be shorter than n, cap the index:

List<Player> top = ranked.subList(0, Math.min(n, ranked.size()));

Without the cap, asking for more elements than exist throws IndexOutOfBoundsException. If you need an independent list, wrap it: new ArrayList<>(ranked.subList(0, k)).