SyntaxPilot
Courses/Java/Lesson 34

Java · Lesson 34 of 51 · 10 min

Comparable vs Comparator, sorting

queued

These are the notes for Java episode 34. On results day the principal wants a rank list (by marks) and the class teacher wants the attendance register (by name): the same students, two orders. Collections.sort works for numbers and Strings but won't even compile for our own Student class, because Java doesn't know what "smaller" means for a student. We invent Comparable (the order written inside the class), dodge the subtraction overflow trap, then invent Comparator (orders that live outside the class), build them with comparing, reversed and thenComparing, fix episode 33's priority queue, and meet the TreeSet that loses items. Every example was run with javac 21.

Sorting numbers and Strings just works

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(List.of(72, 95, 64, 88));
        Collections.sort(marks);
        System.out.println(marks);
        List<String> names = new ArrayList<>(List.of("Ravi", "asha", "Meena", "Kabir"));
        Collections.sort(names);
        System.out.println(names);
    }
}

Output:

[64, 72, 88, 95]
[Kabir, Meena, Ravi, asha]

Integer and String already know how to compare themselves. Strings compare character codes, and every capital letter (A–Z = 65–90) comes before every small letter (a–z = 97–122), so "asha" sorts last. The fix is at the end of these notes.

The problem: sorting your own class

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Student {
    String name;
    int marks;
    Student(String name, int marks) { this.name = name; this.marks = marks; }
    public String toString() { return name + ":" + marks; }
}

public class Main {
    public static void main(String[] args) {
        List<Student> cls = new ArrayList<>();
        cls.add(new Student("Ravi", 72));
        cls.add(new Student("Asha", 95));
        cls.add(new Student("Meena", 64));
        Collections.sort(cls);
        System.out.println(cls);
    }
}

Output:

Main.java:18: error: no suitable method found for sort(List<Student>)
        Collections.sort(cls);
                   ^
    method Collections.<T#1>sort(List<T#1>) is not applicable
      (inference variable T#1 has incompatible bounds
        equality constraints: Student
        upper bounds: Comparable<? super T#1>)
    method Collections.<T#2>sort(List<T#2>,Comparator<? super T#2>) is not applicable
      (cannot infer type-variable(s) T#2
        (actual and formal argument lists differ in length))
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<? super T#1> declared in method <T#1>sort(List<T#1>)
    T#2 extends Object declared in method <T#2>sort(List<T#2>,Comparator<? super T#2>)
1 error

Collections.sort(List<T>) requires T extends Comparable<? super T> ("upper bounds: Comparable"). Should Asha come before Ravi by name, marks or roll number? Java refuses to guess.

Comparable: the order inside the class

A book In Java
Every page carries its own number the class implements Comparable<T>: the natural order
Page 12 vs page 40 compareTo(other) returns negative / zero / positive
Anyone can put shuffled pages back Collections.sort calls compareTo
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Student implements Comparable<Student> {
    String name;
    int marks;
    Student(String name, int marks) { this.name = name; this.marks = marks; }
    public String toString() { return name + ":" + marks; }

    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.marks, other.marks);
    }
}

public class Main {
    public static void main(String[] args) {
        List<Student> cls = new ArrayList<>();
        cls.add(new Student("Ravi", 72));
        cls.add(new Student("Asha", 95));
        cls.add(new Student("Meena", 64));
        Collections.sort(cls);
        System.out.println(cls);
        System.out.println(cls.get(0).compareTo(cls.get(2)));
    }
}

Output:

[Meena:64, Ravi:72, Asha:95]
-1

The compareTo contract

a.compareTo(b) returns:

Result Meaning
negative a comes before b
zero same position (equal for ordering)
positive a comes after b

Only the sign matters, not the size. It should be consistent: if a < b then b > a, and if a < b and b < c then a < c. String, Integer, LocalDate and enums are all Comparable. TreeSet, TreeMap, PriorityQueue, Collections.sort and Arrays.sort use the natural order when you give them no Comparator.

The subtraction trap

A popular shortcut is return this.profit - o.profit;. It works until the difference overflows:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Startup implements Comparable<Startup> {
    String name;
    int profit;                                  // in rupees
    Startup(String name, int profit) { this.name = name; this.profit = profit; }
    public String toString() { return name; }
    public int compareTo(Startup o) { return this.profit - o.profit; }   // shortcut?
}

public class Main {
    public static void main(String[] args) {
        List<Startup> list = new ArrayList<>();
        list.add(new Startup("ChaiCo", 2_000_000_000));
        list.add(new Startup("LossKart", -1_000_000_000));
        list.add(new Startup("TiffinBox", 5_000));
        Collections.sort(list);
        System.out.println(list);
        System.out.println(2_000_000_000 - (-1_000_000_000));
    }
}

Output:

[ChaiCo, LossKart, TiffinBox]
-1294967296

2,000,000,000 - (-1,000,000,000) = 3,000,000,000, which doesn't fit in an int (max 2,147,483,647, episode 2), so it wraps to a negative number and the sort is silently wrong. Never subtract in compareTo/compare; use Integer.compare(a, b), Long.compare, Double.compare.

One class, one compareTo

  • Rank list: by marks → compareTo ✓
  • Attendance register: by name → ?
  • Hostel list: by city → ?

A class can have only one compareTo, and you can't add one to a class you didn't write. The order has to live outside the class.

Comparator: orders outside the class

A talent show In Java
The same contestants the objects; Student doesn't change
A judge with one rule a Comparator<T> with compare(a, b)
Swap the judge → a new ranking pass a different comparator to sort
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Student implements Comparable<Student> {
    String name;
    int marks;
    Student(String name, int marks) { this.name = name; this.marks = marks; }
    public String toString() { return name + ":" + marks; }
    public int compareTo(Student o) { return Integer.compare(marks, o.marks); }
}

class ByName implements Comparator<Student> {
    public int compare(Student a, Student b) { return a.name.compareTo(b.name); }
}

public class Main {
    public static void main(String[] args) {
        List<Student> cls = new ArrayList<>(List.of(new Student("Ravi", 72),
                new Student("Asha", 95), new Student("Meena", 64)));
        cls.sort(new ByName());
        System.out.println("By name:  " + cls);
        cls.sort(null);                      // null = natural order (compareTo)
        System.out.println("By marks: " + cls);
    }
}

Output:

By name:  [Asha:95, Meena:64, Ravi:72]
By marks: [Meena:64, Ravi:72, Asha:95]

list.sort(null) (or Collections.sort(list)) uses the natural order.

Ready-made comparators (Java 8+)

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

record Student(String name, String city, int marks) {}

public class Main {
    public static void main(String[] args) {
        List<Student> cls = new ArrayList<>(List.of(
                new Student("Ravi", "Pune", 72), new Student("Asha", "Delhi", 95),
                new Student("Meena", "Pune", 95), new Student("Kabir", "Delhi", 64)));
        cls.sort(Comparator.comparing(Student::name));
        System.out.println(cls.get(0).name() + " first by name");
        cls.sort(Comparator.comparingInt(Student::marks).reversed()
                           .thenComparing(Student::name));
        for (Student s : cls) System.out.println(s.marks() + " " + s.name());
    }
}

Output:

Asha first by name
95 Asha
95 Meena
72 Ravi
64 Kabir
Builder Meaning
Comparator.comparing(Student::name) compare by a key (must be Comparable)
Comparator.comparingInt(Student::marks) by an int key, no boxing
.reversed() flip the order
.thenComparing(Student::name) break ties with a second key
Comparator.naturalOrder() / reverseOrder() natural order / reversed
Comparator.nullsFirst(...) / nullsLast(...) decide where null goes

Student::name is a method reference ("call name() on each student"); episode 36 covers it fully.

Fixing episode 33: a PriorityQueue of objects

import java.util.Comparator;
import java.util.PriorityQueue;

record Patient(String name, int severity) {}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Patient> er =
                new PriorityQueue<>(Comparator.comparingInt(Patient::severity));
        er.offer(new Patient("Ravi", 4));
        er.offer(new Patient("Asha", 1));
        er.offer(new Patient("Kabir", 3));
        while (!er.isEmpty()) System.out.print(er.poll().name() + " ");
        System.out.println();
    }
}

Output:

Asha Kabir Ravi

TreeSet, TreeMap and PriorityQueue take a Comparator in their constructor.

The TreeSet trap: compare = 0 means duplicate

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

record Student(String name, int marks) {}

public class Main {
    public static void main(String[] args) {
        Set<Student> rank = new TreeSet<>(Comparator.comparingInt(Student::marks));
        rank.add(new Student("Asha", 95));
        rank.add(new Student("Meena", 95));
        rank.add(new Student("Ravi", 72));
        System.out.println(rank.size() + " " + rank);
    }
}

Output:

2 [Student[name=Ravi, marks=72], Student[name=Asha, marks=95]]

A TreeSet (and TreeMap) never calls equals. If the comparator returns 0, the new item is treated as a duplicate and dropped: Meena (95) vanished because Asha also has 95. Make the comparator distinguish everything that should be distinct:

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

record Student(String name, int marks) {}

public class Main {
    public static void main(String[] args) {
        Set<Student> rank = new TreeSet<>(Comparator.comparingInt(Student::marks).reversed()
                                                    .thenComparing(Student::name));
        rank.add(new Student("Asha", 95));
        rank.add(new Student("Meena", 95));
        rank.add(new Student("Ravi", 72));
        System.out.println(rank.size() + " " + rank);
    }
}

Output:

3 [Student[name=Asha, marks=95], Student[name=Meena, marks=95], Student[name=Ravi, marks=72]]

Stable sorting and case-insensitive order

import java.util.Arrays;
import java.util.Comparator;

record Order(int id, String item) {}

public class Main {
    public static void main(String[] args) {
        Order[] orders = { new Order(1, "samosa"), new Order(2, "chai"),
                           new Order(3, "samosa"), new Order(4, "chai") };
        Arrays.sort(orders, Comparator.comparing(Order::item));
        for (Order o : orders) System.out.print(o.item() + "#" + o.id() + " ");
        System.out.println();
        String[] names = { "ravi", "Asha", "meena", "Kabir" };
        Arrays.sort(names, String.CASE_INSENSITIVE_ORDER);
        System.out.println(Arrays.toString(names));
    }
}

Output:

chai#2 chai#4 samosa#1 samosa#3 
[Asha, Kabir, meena, ravi]
  • Sorting objects (Collections.sort, List.sort, Arrays.sort on objects) is stable: equal items keep their original order (TimSort). Sorting primitives (int[]) uses a different algorithm, where stability doesn't matter.
  • String.CASE_INSENSITIVE_ORDER ignores capitals.

Comparable vs Comparator

Comparable Comparator
Lives inside the class outside, a separate object
Method compareTo(T other) compare(T a, T b)
Package java.lang java.util
How many orders one, the natural order as many as you like
Classes you can't edit no yes
Used by sort(list), TreeSet, TreeMap, PriorityQueue by default sort(list, cmp), new TreeSet<>(cmp), ...

Rule of thumb: Comparable for the obvious order (if there is one), Comparators for everything else.

Common mistakes (and the real error messages)

Mistake What you see Why Fix
Collections.sort(students) without Comparable error: no suitable method found for sort(List<Student>) no natural order implements Comparable<Student> or pass a Comparator
return this.profit - o.profit; no error; [ChaiCo, LossKart, TiffinBox] int overflow Integer.compare(a, b)
new TreeSet<>(comparingInt(Student::marks)) no error; size 2, Meena lost compare = 0 means duplicate .thenComparing(Student::name)
Collections.sort(names) with mixed case no error; [Kabir, Meena, Ravi, asha] capitals come first String.CASE_INSENSITIVE_ORDER
new PriorityQueue<Patient>() ClassCastException: ... cannot be cast to class java.lang.Comparable no order pass a Comparator

Mini project: results day

One list of students, three orders: rank list, attendance register, and city-wise hostel list.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

record Student(int roll, String name, String city, int marks) implements Comparable<Student> {
    public int compareTo(Student o) { return Integer.compare(roll, o.roll); }   // natural order: roll number
}

public class Main {
    public static void main(String[] args) {
        List<Student> cls = new ArrayList<>(List.of(
                new Student(3, "Ravi", "Pune", 72), new Student(1, "Asha", "Delhi", 95),
                new Student(4, "Meena", "Pune", 95), new Student(2, "Kabir", "Delhi", 64)));

        cls.sort(null);
        System.out.print("By roll: ");
        for (Student s : cls) System.out.print(s.roll() + " " + s.name() + "  ");

        cls.sort(Comparator.comparingInt(Student::marks).reversed().thenComparing(Student::name));
        System.out.print("\nRank:    ");
        for (int i = 0; i < cls.size(); i++) System.out.print((i + 1) + "." + cls.get(i).name() + "  ");

        cls.sort(Comparator.comparing(Student::city).thenComparing(Student::name));
        System.out.print("\nHostel:  ");
        for (Student s : cls) System.out.print(s.city() + "/" + s.name() + "  ");
        System.out.println();
    }
}

Output:

By roll: 1 Asha  2 Kabir  3 Ravi  4 Meena  
Rank:    1.Asha  2.Meena  3.Ravi  4.Kabir  
Hostel:  Delhi/Asha  Delhi/Kabir  Pune/Meena  Pune/Ravi

Practice

  1. Sort employees by salary (highest first), then by name.
  2. Make a Book class Comparable by title.
  3. Sort ["kiwi", "banana", "fig", "cherry"] by their last letter.
  4. A PriorityQueue of tasks ordered by deadline (an int day number).
Solutions
import java.util.*;

record Employee(String name, int salary) {}
record Book(String title) implements Comparable<Book> {
    public int compareTo(Book o) { return title.compareTo(o.title); }
}
record Task(String name, int deadline) {}

public class Main {
    public static void main(String[] args) {
        List<Employee> e = new ArrayList<>(List.of(new Employee("Ravi", 50000),
                new Employee("Asha", 70000), new Employee("Kabir", 50000)));
        e.sort(Comparator.comparingInt(Employee::salary).reversed().thenComparing(Employee::name));
        System.out.println(e);

        List<Book> b = new ArrayList<>(List.of(new Book("Wings of Fire"), new Book("Godan"), new Book("Malgudi Days")));
        Collections.sort(b);
        System.out.println(b);

        List<String> w = new ArrayList<>(List.of("kiwi", "banana", "fig", "cherry"));
        w.sort(Comparator.comparing(s -> s.charAt(s.length() - 1)));
        System.out.println(w);

        PriorityQueue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::deadline));
        tasks.offer(new Task("report", 5)); tasks.offer(new Task("bills", 2)); tasks.offer(new Task("exam", 3));
        while (!tasks.isEmpty()) System.out.print(tasks.poll().name() + " ");
        System.out.println();
    }
}

Output:

[Employee[name=Asha, salary=70000], Employee[name=Kabir, salary=50000], Employee[name=Ravi, salary=50000]]
[Book[title=Godan], Book[title=Malgudi Days], Book[title=Wings of Fire]]
[banana, fig, kiwi, cherry]
bills exam report

(s -> s.charAt(...) is a lambda, episode 36.)

Quick quiz

List<String> w = new ArrayList<>(List.of("kiwi", "fig", "apple", "pear"));
w.sort(Comparator.comparingInt(String::length)
        .thenComparing(Comparator.reverseOrder()));
System.out.println(w);

A) [fig, kiwi, pear, apple] B) [fig, pear, kiwi, apple] C) [apple, kiwi, pear, fig] D) [fig, apple, kiwi, pear]

Answer

B. Shortest first: fig (3). kiwi and pear tie on 4 letters, and reverse alphabetical order puts pear first. Then apple (5).

[fig, pear, kiwi, apple]

Interview questions

  1. Comparable vs Comparator? Comparable: compareTo inside the class, one natural order, java.lang. Comparator: compare(a, b) outside, many orders, works for classes you can't modify, java.util.
  2. What does compareTo return? Negative, zero or positive: before, same, after. Only the sign matters.
  3. Why not return a - b? Integer overflow can flip the sign; use Integer.compare.
  4. What does "consistent with equals" mean? compareTo returns 0 exactly when equals is true. If not, sorted sets/maps treat compare-equal items as duplicates.
  5. How do you sort descending? .reversed(), Comparator.reverseOrder() or Collections.reverseOrder().
  6. How do you sort by two fields? comparing(first).thenComparing(second).
  7. Is Collections.sort stable? Yes for objects (TimSort): equal elements keep their order.
  8. Which algorithm does Arrays.sort use? Dual-pivot quicksort for primitives, TimSort for objects.
  9. Can a lambda be a Comparator? Yes: Comparator is a functional interface, e.g. (a, b) -> a.name().compareTo(b.name()).

Glossary

Term Meaning Example
Sorting Putting items in order rank list
Natural order The built-in order of a type numbers ascending, Strings A–Z
Comparable Interface for objects that compare themselves implements Comparable<Student>
compareTo The Comparable method: negative / zero / positive a.compareTo(b)
Integer.compare Overflow-safe comparison of two ints Integer.compare(x, y)
Integer overflow A result too big for int wraps around 2e9 - (-1e9) → negative
Comparator A separate object that compares two objects new ByName()
compare(a, b) The Comparator method a.name.compareTo(b.name)
Comparator.comparing Builds a comparator from a key comparing(Student::name)
comparingInt Same, for an int key comparingInt(Student::marks)
reversed Flips a comparator's order highest first
thenComparing Tie-breaker marks, then name
Method reference A method passed as a value (episode 36) Student::name
Stable sort Equal items keep their original order chai#2 before chai#4
CASE_INSENSITIVE_ORDER Compares Strings ignoring case asha before Kabir
Consistent with equals compare = 0 exactly when equals is true needed for TreeSet
TimSort Java's stable sort for objects Collections.sort

Summary

  • Collections.sort works for types with a natural order; your own class needs one.
  • Comparable: compareTo inside the class; negative / zero / positive; never subtract, use Integer.compare.
  • Comparator: compare(a, b) outside the class; any number of orders, even for classes you can't edit.
  • Build comparators with comparing, comparingInt, reversed, thenComparing.
  • TreeSet, TreeMap and PriorityQueue accept a Comparator; a comparator returning 0 makes a TreeSet drop the item.
  • Object sorting is stable; String.CASE_INSENSITIVE_ORDER ignores capitals.
  • Next: data disappears when the program ends: File I/O and NIO (episode 35).