Java collections algorithms

›Short versionOpen if you only have a minute.

java.util.Collections holds static algorithms: sort, binarySearch, min, max, frequency, copy, and others.
sort is in place, stable, and O(n log n). It bumps the list’s modification count.
binarySearch is O(log n) on a random-access list that is already sorted in the same order.
A missing key returns (−(insertion point) − 1). An unsorted list yields a meaningless index and no exception.
min, max, and frequency are linear scans. A TreeSet already knows its ends in logarithmic time.
copy requires the destination to be at least as long as the source. It overwrites; it does not append.

The are the methods you reach for once a list or a set already exists. They do not invent a new structure. They state a cost, and they state what must already be true of the data.

and are the pair people split apart. The search is logarithmic only after the sort, only with the same ordering, and only when index access itself is cheap.

Preconditions are the complexity

binarySearch on an ArrayList does about log n comparisons. Each comparison on a LinkedList starts with a linear index walk, so the same call is no longer a cheap follow-up to sort. Sort into an ArrayList if you intend to search it this way.

and always scan. That is fine once. It is the wrong inner loop. A HashMap counted in one pass replaces a frequency call per word. A TreeSet’s first and last replace min and max when the set is already sorted.

fails when the destination is shorter than the source, rather than growing it. shuffle and rotate rearrange a list in place and count as structural changes for a fail-fast iterator. reverse is linear. None of these methods lock the collection.

Sort, then search, then a linear count

AlgorithmsDemo.java

List<String> names = new ArrayList<>(List.of("Lin", "Ada", "Grace"));
Comparator<String> order = String.CASE_INSENSITIVE_ORDER;
Collections.sort(names, order);                         // stable, O(n log n)

int at = Collections.binarySearch(names, "grace", order);
// at >= 0 means found; at < 0 encodes the insertion point

int graces = Collections.frequency(names, "Grace");    // linear equals scan
String first = Collections.min(names, order);          // linear, unless you have a TreeSet

binarySearch returns -1. Is the key present, and what is the insertion point?

The key is absent, because the result is negative. The insertion point is 0: −1 equals (−(0) − 1). The key would be inserted at the front and the sorted order would hold. An index of 0 would have meant the key is present at the front.