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.sorton 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_ORDERignores 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
- Sort employees by salary (highest first), then by name.
- Make a
BookclassComparableby title. - Sort
["kiwi", "banana", "fig", "cherry"]by their last letter. - A PriorityQueue of tasks ordered by deadline (an
intday 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
- Comparable vs Comparator? Comparable:
compareToinside the class, one natural order,java.lang. Comparator:compare(a, b)outside, many orders, works for classes you can't modify,java.util. - What does compareTo return? Negative, zero or positive: before, same, after. Only the sign matters.
- Why not
return a - b? Integer overflow can flip the sign; useInteger.compare. - What does "consistent with equals" mean?
compareToreturns 0 exactly whenequalsis true. If not, sorted sets/maps treat compare-equal items as duplicates. - How do you sort descending?
.reversed(),Comparator.reverseOrder()orCollections.reverseOrder(). - How do you sort by two fields?
comparing(first).thenComparing(second). - Is Collections.sort stable? Yes for objects (TimSort): equal elements keep their order.
- Which algorithm does Arrays.sort use? Dual-pivot quicksort for primitives, TimSort for objects.
- Can a lambda be a Comparator? Yes:
Comparatoris 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.sortworks for types with a natural order; your own class needs one.- Comparable:
compareToinside the class; negative / zero / positive; never subtract, useInteger.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_ORDERignores capitals. - Next: data disappears when the program ends: File I/O and NIO (episode 35).