Java Collections Sort: Comparator and Comparable

When you need to order the elements of a List in Java, the standard approach is the java collections sort utility: Collections.sort(list) for natural ordering, or Collections.sort(list, comparator) when the default order does not match your requirement. Since Java 8, List also exposes its own sort(Comparator) method, which delegates to the same underlying sorting routine. Understanding how these methods behave, what they require from your element types, and where they fail is the practical part of sorting collections in real code.

The Two Entry Points for Sorting a List

Collections.sort has existed since Java 1.2 and accepts any List whose elements are mutually comparable. The instance method List.sort was added in Java 8 and is the preferred call site in modern code because it reads naturally and does not require the utility class.

List<String> names = new ArrayList<>(List.of("carol", "alice", "bob"));
Collections.sort(names);
System.out.println(names); // [alice, bob, carol]

List<Integer> numbers = new ArrayList<>(List.of(3, 1, 2));
numbers.sort(null);
System.out.println(numbers); // [1, 2, 3]

Passing null as the comparator to List.sort means "use natural ordering," which is the same as relying on the elements' Comparable implementation. Both methods sort the list in place; neither returns a new list. If you need the original order preserved, copy the list before sorting.

Natural Ordering and the Comparable Interface

For Collections.sort(list) to work without a comparator, every element must implement Comparable. The interface requires a single method, compareTo, which returns a negative integer, zero, or a positive integer depending on whether the current instance is less than, equal to, or greater than the argument.

public class Task implements Comparable<Task> {
    private final int priority;
    private final String name;

    public Task(int priority, String name) {
        this.priority = priority;
        this.name = name;
    }

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

    // getters omitted
}

Using Integer.compare instead of manual subtraction avoids overflow problems when the values are far apart. The compareTo implementation must be consistent with equals: if a.compareTo(b) == 0, then a.equals(b) should also be true. Violating this rule produces unpredictable behavior in sorted collections and in TreeSet or TreeMap, which rely on compareTo for membership checks.

Custom Ordering with Comparator

When the natural order is not what you need, or when the class does not implement Comparable, pass a Comparator to the sort method. A comparator is a separate strategy that defines the ordering without modifying the element class.

List<Task> tasks = new ArrayList<>();
tasks.add(new Task(2, "review"));
tasks.add(new Task(1, "deploy"));
tasks.add(new Task(1, "build"));

tasks.sort(Comparator.comparingInt(Task::getPriority)
        .thenComparing(Task::getName));

The lambda-free form reads well for single criteria, but chained comparators are where the real value appears. thenComparing adds a secondary key when the primary keys are equal, which makes the ordering deterministic. Without it, the relative order of tasks with the same priority depends on the sort algorithm's stability and the original list order.

Sorting Maps and Other Collection Types

A Map is not a Collection in the Java type hierarchy, and it has no inherent element order. Sorting a map means sorting one of its views: the keys, the values, or the entries. The common pattern is to copy the entry set into a list and sort that list.

Map<String, Integer> scores = new HashMap<>();
scores.put("alice", 90);
scores.put("bob", 75);
scores.put("carol", 95);

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

After sorting, you can iterate the list to produce an ordered output. If you need a map structure that maintains order continuously, TreeMap with a custom comparator is the better choice, because it keeps keys sorted on every insertion rather than requiring an explicit sort pass.

Performance and Runtime Behavior

The sorting algorithm behind both Collections.sort and List.sort is a stable, adaptive, iterative mergesort, commonly known as TimSort. It runs in O(n log n) time in the worst case and detects partially sorted runs to reduce work on nearly ordered input. Stability matters: equal elements keep their relative order, which is why thenComparing produces predictable results even when the primary key repeats.

Sorting is an in-place operation on the list's backing array, so it does not allocate a second collection of the same size. The main runtime cost is the comparison work, which is why a comparator that performs expensive computation per call, such as parsing a string or fetching a field through a chain of calls, dominates the total time. Precomputing the sort key into a small wrapper object is a reasonable optimization when the key is costly to derive.

Common Mistakes When Sorting Collections

Sorting an unmodifiable list throws UnsupportedOperationException because the sort mutates the backing array. Lists created by List.of and Arrays.asList are not safe to sort directly; copy them first.

A comparator that returns inconsistent results breaks the sort contract. If compare(a, b) returns different values across calls for the same pair, the algorithm can produce wrong order or, in extreme cases, fail with an IllegalArgumentException about a comparison violating its general contract. The typical cause is comparing a mutable field that changes during the sort, or a comparator that reads from shared state.

Null elements are another frequent failure. The default natural ordering throws NullPointerException when it encounters a null element. If nulls are valid in your data, provide a comparator that handles them explicitly, for example by treating null as smaller than any non-null value.

Choosing Between Comparable and Comparator

The decision is about where the ordering logic belongs. Comparable fixes one natural order inside the class, which is appropriate when the class has an obvious default ordering such as a numeric id or a timestamp. Comparator keeps the ordering outside the class, which is necessary when multiple orderings exist or when you cannot modify the element class.

Use Comparable when the class genuinely owns a single canonical ordering. Use Comparator when the ordering depends on the caller's context, such as a UI table that lets users sort by different columns. The two are not mutually exclusive; a class can implement Comparable for its default order and still be sorted with a Comparator when the caller wants something different.