04 — Ordering: Comparable, Comparator & Sorting

Sorting is the most-used operation in the 150 after hashing, and the place where Java-specific mistakes are most common.

Read this file top to bottom the first time. It is built as one continuous explanation: each part creates the problem that the next part solves. Skipping ahead will leave gaps.

Every behaviour claimed here was verified by running it.

Part 1 — The problem

1.1 Sorting works out of the box, until it doesn't

Sorting a list of numbers or strings just works:

List<Integer> nums = new ArrayList<>(List.of(3, 1, 2));
Collections.sort(nums);                  // [1, 2, 3]

List<String> words = new ArrayList<>(List.of("pear", "apple"));
Collections.sort(words);                 // [apple, pear]

Now try it with a class of your own:

class Employee {
    int id;
    String name;
    String dept;
    int salary;
}

List<Employee> staff = ...;
Collections.sort(staff);                 // ✗ DOES NOT COMPILE

1.2 Why it fails

Sorting is just repeated comparison. To sort, Java must be able to ask: "does a come before b?"

For Integer and String the answer is built in — smaller number first, alphabetical order. For Employee, Java has no idea. Should employees be ordered by ID? By salary? By name? There is no universal answer, so Java refuses to guess.

You have to tell Java what "comes before" means for your class.

1.3 The two ways to tell it

This is the whole subject of this file:

Both exist because they answer different needs:

• Comparable — "an Employee has an obvious default order: by ID." Write it once, and every sort and sorted collection uses it automatically.
• Comparator — "on the payroll screen, order by salary descending; on the directory screen, by name." One order per screen, none of them "the" order.

You will usually implement Comparable for the single canonical order, then write Comparators for everything else.

We'll take them in that order.

Part 2 — Comparable: giving a class one built-in order

2.1 What it is

Comparable is an interface with a single method:

public interface Comparable<T> {
    int compareTo(T other);
}

A class that implements it is announcing: "I know how to compare myself to another one of me." That order is called the class's natural ordering.

2.2 The contract — what compareTo returns

It returns an int, and only the sign matters:

The way to remember it: a.compareTo(b) behaves like a - b.

• If a is smaller, a - b is negative → negative means "a first".
• That's why ascending is the default everywhere in Java.

The actual magnitude is ignored — returning -1 and returning -9999 mean exactly the same thing.

2.3 Implementing it

class Employee implements Comparable<Employee> {
    int id;
    String name;
    String dept;
    int salary;

    Employee(int id, String name, String dept, int salary) {
        this.id = id; this.name = name; this.dept = dept; this.salary = salary;
    }

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.id, other.id);       // natural order = by id, ascending
    }
}

Reading Integer.compare(this.id, other.id): it returns negative if this.id is smaller, zero if equal, positive if larger — exactly the contract.

Use Integer.compare(a, b), not a - b. Subtraction overflows when the values are far apart and silently flips the sign, corrupting the sort. Part 6 covers this.

To sort descending, swap the arguments:

return Integer.compare(other.id, this.id);               // descending

2.4 What you get for free

Once the class is Comparable, all of this works with no extra arguments:

Collections.sort(staff);                 // uses compareTo
staff.sort(null);                        // null comparator means "natural ordering"
Arrays.sort(staffArray);
Collections.max(staff);
Collections.min(staff);

new TreeMap<Employee, String>();         // keys ordered by compareTo
new TreeSet<Employee>();
new PriorityQueue<Employee>();           // smallest by compareTo comes out first

Verified: with compareTo ordering by ID, sorting four employees produced IDs 1, 2, 3, 4.

That breadth is the value of Comparable — you define the order once and every ordered thing in the JDK respects it.

2.5 Ordering by more than one field

"By department; if the same department, then by name; if still tied, by ID."

Compare field by field, and return as soon as one is decisive:

@Override
public int compareTo(Employee other) {
    int c = this.dept.compareTo(other.dept);          // 1st: department
    if (c != 0) return c;                             // decided — stop here

    c = this.name.compareTo(other.name);              // 2nd: name (only if depts tie)
    if (c != 0) return c;

    return Integer.compare(this.id, other.id);        // 3rd: id (only if names also tie)
}

The if (c != 0) return c; pattern is the core idea: a later field is only consulted when all earlier fields tie.

Part 4 shows a much shorter way to express this using Comparator. Once you know it, you can even delegate compareTo to it:

private static final Comparator<Employee> NATURAL =
    Comparator.comparing((Employee e) -> e.dept)
              .thenComparing(e -> e.name)
              .thenComparingInt(e -> e.id);

@Override
public int compareTo(Employee other) { return NATURAL.compare(this, other); }

Verified: this produces Eng/Ann, Eng/Bob, Ops/Ann.

2.6 Classes that are already Comparable

You never need to write compareTo for these:

Integer, Long, Double, Character, Boolean and the other boxed primitives, String, LocalDate, BigDecimal, and all enums.

Two behaviours worth knowing:

• String compares by character code, not dictionary order. So "Zebra".compareTo("apple") is negative — uppercase letters have lower codes than lowercase. Verified. For case-insensitive order use String.CASE_INSENSITIVE_ORDER.
• Enums compare by declaration order (their ordinal), not alphabetically.

2.7 The limitation

compareTo is a method on the class. A class has one of it. So Comparable gives you exactly one order, forever.

That's a problem when you need:

• the same class sorted different ways in different places,
• an order that isn't the "natural" one,
• or ordering for a class you can't edit — a library class, or one owned by another team.

All three need the second mechanism.

Part 3 — Comparator: defining as many orders as you like

3.1 What it is

A Comparator is a separate object whose only job is to compare two things:

public interface Comparator<T> {
    int compare(T a, T b);
}

The difference from Comparable is only about where the code lives:

a.compareTo(b)        // Comparable: the object compares ITSELF to another
compare(a, b)         // Comparator: an outsider compares TWO objects

The return-value contract is identical — negative, zero, positive. Everything you learned in 2.2 still applies.

Because a comparator is just an object, you can make as many as you like, name them, store them, and pass a different one to each sort.

3.2 Writing one directly

Comparator<Employee> bySalary = (a, b) -> Integer.compare(a.salary, b.salary);

staff.sort(bySalary);

a and b are the two employees being compared. Read the lambda as: "given two employees, return negative if a should come first."

Sorting by a different field is a different comparator:

Comparator<Employee> byName = (a, b) -> a.name.compareTo(b.name);
Comparator<Employee> byId   = (a, b) -> Integer.compare(a.id, b.id);

staff.sort(byName);      // directory order
staff.sort(bySalary);    // payroll order

That's the payoff — three orders for one class, which Comparable could never give you.

3.3 The shortcut: Comparator.comparing

Writing (a, b) -> Integer.compare(a.salary, b.salary) gets repetitive. Nearly every comparator has the same shape: pull a field out of both objects, compare those.

Comparator.comparing captures that. You supply only the "pull the field out" half:

Comparator<Employee> bySalary = Comparator.comparingInt(e -> e.salary);

e -> e.salary is a key extractor — given an employee, produce the value to sort on. Java writes the comparison itself.

These two lines are equivalent:

(a, b) -> Integer.compare(a.salary, b.salary)
Comparator.comparingInt(e -> e.salary)

Prefer the second. It's shorter, it can't get the argument order backwards, and it can't overflow.

Method references work as key extractors too, if your class has getters:

Comparator<Employee> byName = Comparator.comparing(Employee::getName);

3.4 comparing vs comparingInt

There are four variants:

Comparator.comparingInt(e -> e.salary);    // int field
Comparator.comparing(e -> e.name);         // String field

Why the primitive versions exist: plain comparing treats the key as an object, so an int field would be boxed into an Integer on every single comparison — millions of throwaway objects in a large sort. comparingInt keeps it primitive.

Plain comparing on an int still works and still sorts correctly; it's just slower. Use the primitive variant when the field is primitive.

3.5 Sorting by a computed value

The key extractor can compute anything — it doesn't have to be a field:

// Points ordered by distance from the origin
Comparator<int[]> byDistance = Comparator.comparingInt(p -> p[0]*p[0] + p[1]*p[1]);

// Words ordered by length
Comparator<String> byLength = Comparator.comparingInt(String::length);

This is why comparators show up constantly in the 150 — the "field" you sort on is often derived, and a key extractor expresses that in one line.

Part 4 — Building bigger comparators

Everything in this part starts from a comparator you already have and modifies it. This is where the real expressive power is — and where the one big trap lives.

4.1 Reversing

Call .reversed():

staff.sort(Comparator.comparingInt((Employee e) -> e.salary).reversed());   // highest paid first

Verified: highest salary (200) came first.

Three other ways to get a descending order, for reference:

// A ready-made reverse-natural comparator (needs the class to be Comparable)
staff.sort(Comparator.reverseOrder());

// Swap the arguments by hand — works, but easy to misread
staff.sort((a, b) -> Integer.compare(b.salary, a.salary));

// Sort ascending, then flip the list
Collections.sort(staff);
Collections.reverse(staff);

Collections.reverse(list) is not a comparator. It physically flips the list's current contents. Comparator.reverseOrder() defines a descending order. Confusing the two is common — see Part 6.

4.2 Sorting by several fields

This is the Comparator version of section 2.5, and it's far shorter. Chain with thenComparing:

staff.sort(
    Comparator.comparing((Employee e) -> e.dept)      // 1st key: department
              .thenComparing(e -> e.name)             // 2nd key: used only when depts tie
              .thenComparingInt(e -> e.id)            // 3rd key: used only when names also tie
);

Verified output: Eng/Ann#3, Eng/Bob#1, Ops/Ann#4, Ops/Cid#2.

How the chain runs: thenComparing is consulted only when everything before it returned 0. Each link is a tie-breaker for the one above it — exactly the if (c != 0) return c; logic from 2.5, written declaratively.

Use thenComparingInt / thenComparingLong / thenComparingDouble for primitive keys, same as in 3.4.

One compile-error to expect

Note the explicit type in the first link: (Employee e) -> e.dept.

Without it, Java usually cannot infer what type the chain is comparing and you get a confusing generics error. Anchoring the type once at the head fixes the whole chain. Method references avoid the issue entirely:

Comparator.comparing(Employee::getDept).thenComparing(Employee::getName)   // no annotation needed

4.3 The reversed() trap

This is the single most common mistake with comparators. Read it carefully.

You want: departments descending, but names ascending within each department. So you write:

Comparator.comparing((Employee e) -> e.dept)
          .thenComparing(e -> e.name)
          .reversed();                             // ← intended: reverse the dept only

It reverses the entire chain. .reversed() wraps up everything built so far and flips it — both keys.

Verified output:

Ops/Cid,  Ops/Ann,  Eng/Bob,  Eng/Ann
└── dept descending ✓        └── but name is descending too ✗

You got departments descending (correct) and names descending (wrong). Neither half of the requirement is safely met, and nothing warns you.

The cause: .reversed() is a method on the whole comparator object. By the time you call it, comparing(dept).thenComparing(name) has already been assembled into a single comparator. Reversing that reverses all of it.

4.4 Reversing only one key

Use the two-argument form of comparing / thenComparing. The second argument says how to order that key specifically:

Comparator.comparing(keyExtractor, keyComparator)

So:

Comparator.comparing((Employee e) -> e.dept, Comparator.reverseOrder())   // this key DESCENDING
          .thenComparing(e -> e.name);                                    // this key ASCENDING

Verified output:

Ops/Ann,  Ops/Cid,  Eng/Ann,  Eng/Bob
└── dept descending ✓  └── name ascending ✓

Each key now carries its own direction, independently.

A three-key example — department ascending, salary descending, name ascending:

staff.sort(
    Comparator.comparing((Employee e) -> e.dept)
              .thenComparing(e -> e.salary, Comparator.reverseOrder())
              .thenComparing(e -> e.name)
);

Verified: Eng/Bob(200), Eng/Ann(100), Ops/Cid(150), Ops/Ann(120).

Rule of thumb: .reversed() is only safe on a single-key comparator. The moment you have a chain, set direction per key with the two-argument form.

4.5 Handling null fields

A plain comparator throws NullPointerException if a key is null. Wrap it to decide where nulls go:

Comparator.nullsFirst(Comparator.naturalOrder());     // nulls at the start
Comparator.nullsLast(Comparator.naturalOrder());      // nulls at the end

Verified: ["b", null, "a"] sorts to [null, a, b] with nullsFirst, and [a, b, null] with nullsLast.

To null-protect one key inside a chain, use it as that key's comparator:

Comparator.comparing(Employee::getName, Comparator.nullsLast(Comparator.naturalOrder()));

Part 5 — Where ordering gets used

Parts 2–4 were about defining an order. This part is about the four places you apply one.

5.1 Lists and arrays

list.sort(comparator);                 // preferred since Java 8
list.sort(null);                       // natural ordering
Collections.sort(list);                // natural ordering
Collections.sort(list, comparator);

Arrays.sort(objArray);                 // natural ordering
Arrays.sort(objArray, comparator);
Arrays.sort(arr, fromIndex, toIndex);  // sort a subrange

You cannot sort int[] with a comparator

Arrays.sort(intArray, (a, b) -> b - a);        // ✗ DOES NOT COMPILE

There is no such overload. Comparators work on objects, and int is a primitive. Three workarounds:

// 1. Box it into Integer[]
Integer[] boxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);
Arrays.sort(boxed, Comparator.reverseOrder());

// 2. Sort ascending, then reverse in place
Arrays.sort(nums);
for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
    int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}

// 3. Negate the values, sort, negate back

But int[][] DOES work with a comparator, because its elements (int[]) are objects:

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));                  // by first column
Arrays.sort(intervals, Comparator.comparingInt((int[] r) -> r[0])
                                 .thenComparingInt(r -> r[1]));               // two keys

Verified: [[1,9],[1,2],[0,5]] → [[0,5],[1,2],[1,9]].

That asymmetry is why interval problems (21) sort cleanly while "sort this int array descending" needs a workaround.

Sorting indices instead of values

When you must process things in sorted order but report results in the original order:

Integer[] idx = new Integer[queries.length];
for (int i = 0; i < queries.length; i++) idx[i] = i;
Arrays.sort(idx, Comparator.comparingInt(i -> queries[i]));   // sort the INDICES by their value

Verified: queries = [30,10,20] gives idx = [1, 2, 0].

Boxed Integer[] is required here — it's the same "no comparator on int[]" rule. This exact technique drives Minimum Interval to Include Each Query (21).

Stability

Stable means equal elements keep their original relative order. Verified: sorting employees by name alone left the two Anns in input order (ID 3 before ID 4).

Primitives get quicksort because two identical ints are indistinguishable — stability is meaningless, so Java uses the faster in-place algorithm.

5.2 TreeMap and TreeSet

These keep their contents sorted at all times, so they need an order at construction.

The default is natural ordering

TreeMap<Employee, String> tm = new TreeMap<>();
tm.put(someEmployee, "x");

If Employee implements Comparable, keys come out in compareTo order. If it doesn't:

Exception in thread "main" java.lang.ClassCastException:
class Employee cannot be cast to class java.lang.Comparable

It throws on the very first put. TreeMap deliberately calls compare(key, key) when inserting into an empty map, purely as a type check — so you fail immediately rather than after the map has filled up. Verified.

PriorityQueue behaves identically: ClassCastException on the first offer.

(Collections.sort(list) catches this earlier still — it won't compile, because its signature demands a Comparable type.)

Supplying a comparator instead

Pass one to the constructor, and the class needn't be Comparable at all:

TreeMap<Employee, String> bySalary =
    new TreeMap<>(Comparator.comparingInt((Employee e) -> e.salary).reversed());

TreeSet<Employee> byDeptThenId = new TreeSet<>(
    Comparator.comparing((Employee e) -> e.dept).thenComparingInt(e -> e.id));

Verified: the bySalary map's firstKey() had salary 200.

A TreeMap's comparator is fixed at construction and cannot be changed afterwards. To get the opposite order, use the view treeMap.descendingMap() (or treeSet.descendingSet()) — no copying. To get a genuinely different order, build a new TreeMap.

The deduplication trap

A TreeSet decides two elements are duplicates when the comparator returns 0. It never calls equals.

TreeSet<Employee> ts = new TreeSet<>(Comparator.comparing(e -> e.dept));
ts.addAll(fourEmployeesAcrossTwoDepartments);
ts.size();          // 2  ← verified. Two employees silently vanished.

The comparator only looked at dept, so two employees in the same department compared as equal — and a Set discards duplicates. Same for TreeMap keys: a comparator-equal key overwrites the existing entry.

The fix is to make the comparator a total order — one that never returns 0 for genuinely different elements. End every chain with a unique field:

new TreeSet<>(Comparator.comparing((Employee e) -> e.dept)
                        .thenComparingInt(e -> e.id));     // id guarantees uniqueness

Verified: this keeps all four.

This is what "consistent with equals" means, and it's why compareTo returning 0 should normally coincide with equals returning true. BigDecimal famously breaks it: new BigDecimal("1.0").equals(new BigDecimal("1.00")) is false, but compareTo returns 0 — so a TreeSet keeps one and a HashSet keeps both. See 05.

5.3 PriorityQueue

Same two options — natural ordering, or a comparator in the constructor:

PriorityQueue<Employee> lowestPaidFirst =
    new PriorityQueue<>(Comparator.comparingInt(e -> e.salary));

PriorityQueue<Employee> highestPaidFirst =
    new PriorityQueue<>(Comparator.comparingInt((Employee e) -> e.salary).reversed());

Two differences from TreeSet:

• It does not deduplicate. Ties are kept, and their relative order is unspecified.
• Only the head is ordered. Iterating a PriorityQueue does not give sorted order; only repeated poll() does.

See 14 for how heaps are used in the 150.

5.4 Sorting a HashMap

A HashMap has no order at all. To get an ordered result you extract the entries, sort them, and collect into something that preserves order.

By value, descending

List<Map.Entry<String, Integer>> entries = new ArrayList<>(freq.entrySet());
entries.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));

for (Map.Entry<String, Integer> e : entries) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}

Map.Entry.comparingByValue() and Map.Entry.comparingByKey() are ready-made comparators for entries — no key extractor needed.

The hand-written equivalent:

entries.sort((a, b) -> Integer.compare(b.getValue(), a.getValue()));   // b, a = descending

Breaking ties by key

entries.sort(Map.Entry.<String,Integer>comparingByValue(Comparator.reverseOrder())
                      .thenComparing(Map.Entry.comparingByKey()));

The explicit <String,Integer> is required. Java cannot infer the entry type from a static method reference at the head of a chain, and omitting it produces a compile error that is hard to read. Supply it and the chain works.

Keeping the order in a Map

Putting sorted entries back into a HashMap would scramble them again. Use a LinkedHashMap, which preserves insertion order:

LinkedHashMap<String, Integer> sorted = new LinkedHashMap<>();
freq.entrySet().stream()
    .sorted(Map.Entry.<String,Integer>comparingByValue(Comparator.reverseOrder())
                     .thenComparing(Map.Entry.comparingByKey()))
    .forEach(e -> sorted.put(e.getKey(), e.getValue()));

Verified: {a=3, b=1, c=5, d=3} → {c=5, a=3, d=3, b=1} — by value descending, a before d on the tie.

The stream-collector form does the same thing:

LinkedHashMap<String,Integer> sorted = freq.entrySet().stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
                              (a, b) -> a, LinkedHashMap::new));

The last two arguments are not optional decoration. (a, b) -> a resolves duplicate keys, and LinkedHashMap::new is what preserves order — omit it and Collectors.toMap gives you a HashMap, discarding the ordering you just computed.

By key

If you need key order repeatedly, don't re-sort — copy into a TreeMap once:

TreeMap<String, Integer> byKey = new TreeMap<>(freq);              // natural key order

TreeMap<String, Integer> byKeyDesc = new TreeMap<>(Comparator.reverseOrder());
byKeyDesc.putAll(freq);                                            // descending key order

Which to choose: sorting a HashMap's entries costs O(n log n) once. A TreeMap costs O(log n) per operation but is always ordered and supports floorKey/ceilingKey. Sort once if you need the order once; use a TreeMap if you need it continuously (02).

Part 6 — Reference

6.1 Which one do I need?

Do I need to order objects of some class?
│
├─ Is there one obvious "default" order, and can I edit the class?
│     → implement Comparable, write compareTo
│
├─ Do I need several different orders?
│     → write a Comparator for each
│
├─ Can I not edit the class (library / another team's code)?
│     → Comparator (the only option)
│
└─ Both? Perfectly normal:
      Comparable for the default, Comparators for the alternatives.

6.2 Recipe table

6.3 The ten traps

1. .reversed() reverses the whole chain, not just the last key. Use the two-argument comparing for per-key direction. (4.3)
2. TreeMap/TreeSet/PriorityQueue of a non-Comparable type throws ClassCastException on the FIRST insert — at runtime, not compile time. (5.2)
3. TreeSet deduplicates by the comparator, not equals — a non-total comparator silently drops elements. (5.2)
4. Arrays.sort(int[], comparator) doesn't exist. Box first. (5.1)
5. (a, b) -> a - b overflows and flips sign. Use Integer.compare. (2.3)
6. Collecting sorted entries into a HashMap loses the order. Use LinkedHashMap. (5.4)
7. Anchor the type in the first comparing — (Employee e) -> e.dept — or type inference fails through the chain. (4.2)
8. Collections.reverse ≠ Comparator.reverseOrder — one flips a list, the other defines an order. (4.1)
9. A TreeMap's comparator can't be changed after construction. (5.2)
10. Primitive sorts aren't stable; object sorts are. (5.1)

6.4 The contract, for reference

A comparator must be:

• Antisymmetric — compare(a,b) and compare(b,a) have opposite signs.
• Transitive — if a < b and b < c, then a < c.
• Consistent — if compare(a,b) == 0, then a and b compare identically against every other element.

Violating these can throw IllegalArgumentException: Comparison method violates its general contract! — TimSort detects some breaches at runtime. The usual cause is trap #5, integer overflow in a subtraction comparator.