Sorting Java Collections

Sorting a Java collection is one operation with three idiomatic entry points: Collections.sort(list), list.sort(comparator), and stream.sorted(). All three share the same underlying algorithm — a stable, adaptive mergesort (TimSort variant) with O(n log n) worst case — and the same dependency on either a Comparable element type or a Comparator you provide. The differences are where the result lives and what the call site reads like.

This chapter is about lists. Sets and maps have their own ways of staying sorted (TreeSet, TreeMap) — they sort on insertion, not after the fact. If you have a HashSet you want sorted, the standard pattern is new ArrayList<>(set) followed by a sort.

The three entry points

Collections.sort(list) — the original

Collections.sort(list);                  // natural ordering — list element type must implement Comparable
Collections.sort(list, comparator);       // explicit comparator

In place. Stable. Returns void. Predates Java 8 and is still common because it reads obviously and it predates the alternatives. Internally delegates to list.sort on modern JDKs.

list.sort(comparator) — the modern instance method

list.sort(null);                          // natural ordering — null means "use Comparable"
list.sort(comparator);

Added in Java 8 directly on List<E>. Same semantics as Collections.sort — in place, stable, returns void. The instance form lets a list implementation override the algorithm if it can do better (e.g. LinkedList doesn't, but a custom list might).

Use list.sort for new code. It's shorter, reads better with method references, and doesn't require importing Collections.

stream.sorted() — when you want a new sequence

List<Person> sorted = people.stream()
                            .sorted(Comparator.comparingInt(Person::age))
                            .toList();

Returns a new sorted stream — the input is untouched. Use this when:

• The input is immutable (List.of(...)) and list.sort would throw.
• You're building a pipeline anyway (map, filter, then sort).
• You don't want to mutate the source list.

The cost is an extra allocation of the sorted result. For short lists it's negligible; for a million-element list a Collections.sort mutating in place is cheaper than a stream().sorted().toList() that copies the whole thing.

Natural ordering vs comparator

Both Collections.sort(list) and list.sort(null) use the element type's natural ordering, defined by its Comparable implementation:

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

If the element type doesn't implement Comparable, you'll see ClassCastException at runtime — not a compile error, because the cast happens inside the sort. Pass a Comparator explicitly to fix:

List<Person> people = new ArrayList<>(...);
people.sort(Comparator.comparing(Person::name));

Any Comparator from the previous chapter applies — single key, chained keys, reversed, null-safe, the lot.

Stable sort: equal elements keep their order

TimSort is stable: if two elements are equal under the comparator, the one that came first in the input still comes first in the output. That's what lets multi-key sorting work as composed single-key passes:

people.sort(Comparator.comparing(Person::lastName));     // first pass
people.sort(Comparator.comparingInt(Person::age));        // second pass — primary key wins, ties broken by previous order

After both passes, the list is sorted by age primarily and by lastName within each age group. Sorting in reverse order of priority — secondary key first, primary key last — is the trick that makes multi-pass sorting work. Most of the time you'd write the chained comparator from the previous chapter instead; this is the legacy alternative.

Modifiable vs unmodifiable lists

List.of(...), Collections.unmodifiableList(...), and Arrays.asList(array) all return lists you cannot sort in place. list.sort(...) calls list.set(i, x) internally, and immutable lists throw UnsupportedOperationException from that.

Two fixes:

List<String> sorted = original.stream().sorted().toList();   // new immutable, sorted list
List<String> copy   = new ArrayList<>(original); copy.sort(null);

Arrays.asList(...) is a special case: the list is fixed-size but the slots are modifiable, so sort works. add/remove don't.

Primitive lists and the boxing tax

List<Integer> boxes every value. Sorting a million Integers is much slower than sorting a int[]. If the data is primitive, prefer:

int[] data = ...;
Arrays.sort(data);                       // primitive sort: cache-friendly, no boxing

…then convert to a list if you need one later. The same pattern applies to long[], double[], char[]. If you're sorting by a primitive key on objects, use Comparator.comparingInt, comparingLong, comparingDouble to avoid boxing inside the comparator:

people.sort(Comparator.comparingInt(Person::age));     // unboxed key extraction

Collections.sort is in place; sometimes you want a copy

If you want a sorted result without mutating the source:

List<String> sortedCopy = new ArrayList<>(source);
sortedCopy.sort(null);

…or the stream form:

List<String> sortedCopy = source.stream().sorted().toList();

Both work. The first is two lines and zero pipeline overhead. The second is one expression. Pick whichever fits the surrounding code.

Sorting a Map by value

Maps don't have a sort method — there's no "position" on a Map. The idiom is to sort the entry set into a List and then iterate that:

List<Map.Entry<String, Integer>> byCount = scores.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .toList();

If you need the result to be a map that iterates in that order, collect into a LinkedHashMap — its insertion order is its iteration order:

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

The four-arg toMap overload lets you choose the map implementation. Don't skip it — the default is HashMap, which destroys the order you just imposed.

A worked example: in-place sort, stream sort, chained comparator, sorting a map

The program below sorts a list in place, builds a sorted copy with stream().sorted(), applies a chained comparator with a reversed secondary key, then sorts a map by value into a LinkedHashMap that iterates in the sorted order.

What to take from the run:

• The in-place sort picked up the chained comparator and produced age-ascending with salary-descending tie-breakers in one call. No second pass needed.
• The stream form returned a new sorted list and left the source List.of untouched. That's the right pattern when the input is immutable or shared.
• Calling sort on an immutable list threw UnsupportedOperationException. The sort is in place, and "in place" requires mutability.
• The map ranking landed in a LinkedHashMap, so its iteration matches the sort order. If we'd used the three-arg toMap, the result would have been a HashMap and the order would have been lost.

What's next

You can now order any list, and you can produce a sorted copy without mutating the source. Searching is the next operation — finding an element by predicate, by equality, or by binary search on an already-sorted list. The next chapter is Searching Java Collections.

Practice