Part 10 — Comparable vs Comparator Deep Dive¶

This topic is asked in almost every senior Java interview because sorting is fundamental.

Typical interview questions:

• What is the difference between Comparable and Comparator?
• When should you use each?
• How does Collections.sort() work internally?
• What is TimSort?
• What happens if compareTo() is implemented incorrectly?
• Why should a comparator be consistent with equals()?

1. Why Do We Need Sorting?¶

Consider:

List<Integer> list =
    Arrays.asList(30, 10, 20);

Without sorting:

30 10 20

After sorting:

10 20 30

Java provides multiple ways to define the ordering.

2. Comparable¶

Comparable defines the natural ordering of a class.

Interface:

public interface Comparable<T> {

    int compareTo(T other);
}

Example:

class Employee implements Comparable<Employee> {

    private int id;

    Employee(int id) {
        this.id = id;
    }

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

Now:

Collections.sort(employeeList);

works automatically.

3. How compareTo() Works¶

Rule:

Negative → this < other

Zero → equal

Positive → this > other

Example:

5.compareTo(10)

Result:

-1

Meaning:

5 comes before 10

4. Natural Ordering Examples¶

Integer¶

Collections.sort(numbers);

Ascending.

String¶

Collections.sort(names);

Alphabetical.

LocalDate¶

Collections.sort(dates);

Chronological.

5. Comparator¶

Comparator defines an external ordering.

Interface:

public interface Comparator<T> {

    int compare(T o1, T o2);
}

Unlike Comparable, you do not modify the class.

6. Example¶

Employee:

class Employee {

    int id;

    double salary;
}

Sort by salary:

Comparator<Employee> bySalary =
    Comparator.comparingDouble(Employee::getSalary);

employees.sort(bySalary);

The class itself remains unchanged.

7. Comparable vs Comparator¶

8. Multiple Sorting Strategies¶

Employee:

ID

Name

Salary

Age

Possible comparators:

Comparator<Employee> byId

Comparator<Employee> byName

Comparator<Employee> bySalary

Comparator<Employee> byAge

One class.

Many orderings.

9. Lambda Comparator¶

Before Java 8:

Collections.sort(list,
    new Comparator<Employee>() {

        @Override
        public int compare(
                Employee a,
                Employee b) {

            return a.getAge() - b.getAge();
        }
});

Java 8:

list.sort(
    Comparator.comparingInt(Employee::getAge)
);

Cleaner and safer.

10. Reverse Order¶

Ascending:

Comparator.comparing(Employee::getSalary)

Descending:

Comparator.comparing(Employee::getSalary)
          .reversed();

11. Multi-Level Sorting¶

Very common interview topic.

Sort by:

• Department
• Salary
• Name

Comparator<Employee> comparator =
    Comparator
        .comparing(Employee::getDepartment)
        .thenComparing(Employee::getSalary)
        .thenComparing(Employee::getName);

Example:

Before:

IT 5000 Bob

IT 5000 Alice

IT 4000 Tom

After:

IT 4000 Tom

IT 5000 Alice

IT 5000 Bob

12. Comparator Chaining¶

Useful methods:

thenComparing()

reversed()

nullsFirst()

nullsLast()

Example:

Comparator<String> cmp =
    Comparator.nullsLast(String::compareTo);

13. Sorting with Null Values¶

Without handling null:

Collections.sort(list);

May throw:

NullPointerException

Safe:

Comparator<String> comparator =
    Comparator.nullsFirst(
        Comparator.naturalOrder()
    );

14. Comparable Contract¶

The contract requires:

Reflexive¶

a.compareTo(a) == 0

Symmetric Sign¶

If:

a.compareTo(b) < 0

Then:

b.compareTo(a) > 0

Transitive¶

If:

A < B

B < C

Then:

A < C

Violating these rules can cause unpredictable behavior in sorted collections and sorting algorithms.

15. Comparator Consistency with equals()¶

Interview favorite.

Suppose:

Comparator<String> lengthComparator =
    Comparator.comparingInt(String::length);

Now:

TreeSet<String> set =
    new TreeSet<>(lengthComparator);

set.add("cat");

set.add("dog");

Result:

cat

Why?

Both have:

Length = 3

Comparator returns:

0

TreeSet considers them duplicates.

This is why comparators should usually be consistent with equals().

16. Collections.sort()¶

Older style:

Collections.sort(list);

Internally:

List.sort(...)

In modern JDKs, Collections.sort() delegates to List.sort().

17. List.sort()¶

Modern approach:

list.sort(
    Comparator.comparing(Employee::getAge)
);

Preferred over Collections.sort() for readability.

18. TimSort¶

Interview favorite.

Java uses:

TimSort

for sorting objects.

Invented by:

Tim Peters

Originally for Python.

19. Why TimSort?¶

TimSort combines:

Merge Sort

+

Insertion Sort

Advantages:

• Stable
• Fast on partially sorted data
• Excellent real-world performance

20. Stable Sorting¶

Suppose:

Before:

Alice 25

Bob 25

Tom 30

Sort by age.

Result:

Alice 25

Bob 25

Tom 30

Alice remains before Bob.

Relative order of equal elements is preserved.

This is called a stable sort.

21. Primitive Arrays¶

Arrays.sort(int[]);

Does not use TimSort.

It uses a Dual-Pivot Quicksort implementation.

22. Object Arrays¶

Arrays.sort(Employee[]);

Uses:

TimSort

23. Complexity¶

TimSort's best case is O(n) because it detects already sorted or partially sorted runs.

24. Common Mistake¶

Wrong:

return this.salary - other.salary;

Problems:

• Overflow for integers
• Impossible for doubles

Correct:

return Double.compare(
    this.salary,
    other.salary
);

Similarly:

Integer.compare(a, b)
Long.compare(a, b)

25. Production Examples¶

Sort by salary:

employees.sort(
    Comparator.comparingDouble(Employee::getSalary)
);

Descending:

employees.sort(
    Comparator
        .comparingDouble(Employee::getSalary)
        .reversed()
);

Multiple fields:

employees.sort(

    Comparator
        .comparing(Employee::getDepartment)
        .thenComparing(Employee::getAge)
        .thenComparing(Employee::getName)

);

Common Interview Questions¶

Q1. Difference between Comparable and Comparator?¶

Comparable defines the natural ordering inside the class.

Comparator defines external orderings.

Q2. Can a class have multiple Comparables?¶

No.

A class can implement Comparable only once.

Multiple sorting strategies require different Comparator implementations.

Q3. Which is better?¶

Use:

• Comparable for the default/natural ordering.
• Comparator for alternative orderings.

Often, a class has one Comparable implementation and many Comparators.

Q4. Which algorithm does Java use?¶

Objects:

TimSort

Primitive arrays:

Dual-Pivot Quicksort

Q5. Why is TimSort used?¶

Because it is:

• Stable
• Adaptive
• Efficient for partially sorted data
• O(n log n) worst case

Q6. What happens if compareTo() returns inconsistent values?¶

Results can include:

• Incorrect sorting
• Unexpected behavior in TreeMap/TreeSet
• Violated collection invariants

Q7. Why should a comparator be consistent with equals()?¶

Because sorted collections (TreeSet, TreeMap) treat elements as duplicates when the comparator returns 0.

Q8. Is sorting stable?¶

For object sorting with TimSort:

Yes.

For primitive arrays:

The Dual-Pivot Quicksort implementation is not stable.

Q9. Difference between Collections.sort() and Arrays.sort()?¶

Q10. Which sorting method should you use in Java 8+?¶

Prefer:

list.sort(comparator);

It is the modern, idiomatic API.

Senior Interview Scenario¶

Question:

Why does this TreeSet contain only one element?

TreeSet<String> set =
    new TreeSet<>(
        Comparator.comparingInt(String::length)
    );

set.add("cat");

set.add("dog");

Answer:

The comparator returns 0 because both strings have length 3.

TreeSet determines uniqueness using the comparator, not equals().

Therefore, "dog" replaces the logical position of "cat" and is treated as a duplicate.

Key Takeaways¶

• Comparable defines a class's natural ordering.
• Comparator defines external and reusable sorting strategies.
• Comparator chaining (thenComparing) is common in production code.
• Use Integer.compare(), Long.compare(), and Double.compare() instead of subtraction.
• Java uses TimSort for object sorting and Dual-Pivot Quicksort for primitive arrays.
• TimSort is stable and adaptive.
• A comparator returning 0 makes TreeSet and TreeMap treat two keys as equivalent.

Next: Part 11 — Immutable Collections (Java 9+)¶

We'll cover:

• List.of(), Set.of(), Map.of()
• Immutable vs unmodifiable collections
• Collections.unmodifiableList()
• Defensive copying
• Performance and memory benefits
• Production use cases
• Common interview questions