SwadhyAI Notes

All Java notes

Java list sorting

›Short versionOpen if you only have a minute.
  • List.sort reorders the list in place. Collections.sort delegates to it.
  • sort(null) uses Comparable. Any other order is a Comparator, and later searches must use that same comparator.
  • The algorithm is TimSort: stable, O(n log n) worst case, and faster when the list is already nearly ordered.
  • Stability keeps the previous relative order of elements the comparator treats as tied.
  • binarySearch is logarithmic only on a list sorted in the same order. A miss returns (−(insertion point) − 1).
  • Sorting bumps the list’s modification count, so an open iterator fails fast.

Sorting a list means the indexes change so that walking from 0 to the end visits elements in order. does that to the list you already hold. Natural order comes from . Every other order is a .

The platform sort is , and it is . Those two facts decide more real programs than a hand-rolled comparison loop does.

Order is part of the later search

A trusts the order. If you sorted with a comparator and then search with natural order, the index you get can be wrong while looking plausible. Pass the same comparator to both calls.

On an ArrayList the search is logarithmic after the sort’s n log n work. On a LinkedList, binary search still probes by index, and each probe walks the chain, so the “logarithmic” search becomes much more expensive. Sort and search lists you actually index.

To sort by last name and break ties by first name, put the primary key last if you rely on stability, or build one comparator with thenComparing so a single pass defines the whole order. One comparator is easier to hand to binarySearch later.

One comparator for sort and search

SortDemo.java
List<String> names = new ArrayList<>(List.of("Ada", "grace", "Lin"));
Comparator<String> byLower = String.CASE_INSENSITIVE_ORDER;

names.sort(byLower);
int found = Collections.binarySearch(names, "lin", byLower);
// found is an index; a negative result encodes the insertion point

names.sort(Comparator.naturalOrder());
// binarySearch must now use natural order too, or the index is meaningless

binarySearch returns -3. Is the key present, and where would it be inserted?

The key is absent. The insertion point is 2, because −3 equals (−(2) − 1). Inserting at index 2 keeps the sorted order. A return value of 2 would have meant the key sits at index 2.