How do Collections.sort and Collections.binarySearch work, and what are their requirements and complexity?
answer
- sort = in-place, stable; TimSort today, n log n
- natural order needs Comparable, else pass Comparator
- binarySearch requires a pre-sorted list
- not found => -(insertion point) - 1
- slow on LinkedList (no RandomAccess)
basics
~20 sCollections.sort(list) orders a list in place, ascending by the elements' natural order or in the order a Comparator you pass defines. Collections.binarySearch(list, key) finds an element quickly, but only works if the list is already sorted.
solid answer
~40 sCollections.sort sorts a List in place and returns nothing. The one-argument version needs a list of Comparable elements (natural ordering); the two-argument version takes a Comparator. The contract guarantees a stable sort, and the current implementation delegates to List.sort, an adaptive mergesort (TimSort) with n log n comparisons at worst. Collections.binarySearch has a hard precondition: the list must already be sorted in the same order the search uses, otherwise the result is undefined. If the key is found it returns an index, with no guarantee which one among equal elements; if not, it returns (-(insertion point) - 1), a negative value encoding where the key would go. It runs in log n time on RandomAccess lists like ArrayList. A large LinkedList gets an iterator-based search instead: O(log n) comparisons but O(n) link traversals.
code
java · 8 linesList<Integer> nums = new ArrayList<>(List.of(30, 10, 20));
Collections.sort(nums); // [10, 20, 30]
int i = Collections.binarySearch(nums, 20); // 1 (found)
int miss = Collections.binarySearch(nums, 25); // -3 (not found)
int insertAt = -miss - 1; // 2 -> where 25 belongs
// Comparator overload: sort descending
Collections.sort(nums, Comparator.reverseOrder()); // [30, 20, 10]go deeper
Can call Collections.sort and knows binarySearch needs a sorted list; knows sort mutates the list.
Explains Comparable vs Comparator, the stable n log n cost, and decodes the negative not-found return value.
Discusses TimSort, the RandomAccess/LinkedList performance trap, and prefers list.sort over Collections.sort in modern code.
Reasons about sort stability in multi-key pipelines, undefined-behavior contracts of binarySearch, and API evolution toward Stream.sorted/List.sort.
## Sorting a list `Collections.sort` reorders the elements of a `List` **in place** (it mutates the list; it does not return a new one). There are two overloads: - `Collections.sort(List<T>)` — sorts by **natural ordering**. The signature is `<T extends Comparable<? super T>>`, so every element must implement `Comparable`, i.e. have a `compareTo` method. `String`, `Integer`, `LocalDate`, etc. already do. A `List<Foo>` whose `Foo` is not `Comparable` **does not compile**. A `ClassCastException` arises at runtime only where the compiler cannot see the problem: a raw `List`, elements of types that cannot compare to each other, or `list.sort(null)`. - `Collections.sort(List<T>, Comparator<? super T>)` — sorts by the rule you supply. A `Comparator` is an object whose `compare(a, b)` returns negative / zero / positive to mean a < b, a == b, a > b. **What is promised, and what the JDK happens to do.** The contract promises one thing about the algorithm: the sort is *stable*, meaning equal elements keep their original relative order, which is important when sorting by one field after another. The class Javadoc says `sort` "does not have to be a mergesort, but it does have to be stable". The current implementation is **TimSort**, an adaptive, iterative mergesort, and its costs are implementation notes: traditional mergesort performance on random input, so **O(n log n)**, and approximately n comparisons on nearly sorted input. Note that since Java 8 you can also call `list.sort(comparator)` directly (a default method on `List`, where `null` means natural order); `Collections.sort` simply delegates to it now. **What else can fail.** The list must be modifiable but need not be resizable: `Arrays.asList(2, 1)` sorts fine, while `List.of(2, 1)` throws `UnsupportedOperationException`. A comparator that breaks its contract may draw an `IllegalArgumentException`, which the Javadoc marks optional. ## Binary search `Collections.binarySearch(list, key)` (and the comparator overload) finds an element by repeatedly halving the search range: - **Precondition:** the list **must already be sorted** ascending in the same ordering used by the search. If it isn't, the Javadoc calls the results **undefined**. No sortedness check runs, so you normally get a meaningless value and no exception. This is the single most important fact about it. - **Found:** returns the **index** of a matching element. With duplicates there is no guarantee which one. - **Not found:** returns `-(insertion point) - 1`. The *insertion point* is the index of the first element greater than the key, or `list.size()` if every element is smaller. This negative encoding lets you do both lookup and "where would it go" in one call, and the `- 1` makes the result `>= 0` exactly when the key is found, which a plain `-(insertion point)` could not do at index 0. To turn a not-found result into an insertion index, compute `int insertAt = -result - 1;`. **Complexity:** **O(log n)** time on a `RandomAccess` list such as `ArrayList`. But there is a trap: a `LinkedList` must walk links to reach an index. For a large one (5,000 elements or more in the current code), `binarySearch` repositions a `ListIterator` instead of calling `get`, and the Javadoc prices that at **O(log n) comparisons but O(n) link traversals** — effectively linear. Use it on array-backed lists. ## Worked example of the negative return Sorted list `[10, 20, 30]`. Searching for `25` returns `-3`: the insertion point is index 2 (between 20 and 30), and `-(2) - 1 = -3`. Decode with `-(-3) - 1 = 2`. ## Key terms - **Comparable:** an interface giving a type a natural order via `compareTo`. - **Comparator:** a separate object defining an ordering, passed in when natural order is absent or unwanted. - **Stable sort:** preserves relative order of equal elements. - **RandomAccess:** a marker interface signalling fast (generally constant-time) indexed access (ArrayList has it; LinkedList does not). - **Insertion point:** where a missing key would be placed to keep the list sorted.
- What does binarySearch return when the key is absent?It returns -(insertionPoint) - 1, a negative number encoding where the key would be inserted; decode the index with -(result) - 1.
- Why is Collections.sort stable, and when does that matter?The contract requires it: equal elements are not reordered, whatever algorithm sits underneath (TimSort today). Stability matters when chaining sorts — e.g. sort by name then by age keeps name-order within equal ages.
- Calling binarySearch on an unsorted list and trusting the result
- Thinking binarySearch always returns -1 when not found (it encodes the insertion point)
- Assuming sort returns a new list
- Believing binarySearch is O(log n) work on a LinkedList
- Expecting a runtime exception, not a compile error, for a typed list of non-Comparable elements
- Collections.sort and Collections.binarySearch
- Java 1.2
- List.sort default method
- Java 1.8
- RandomAccess marker interface
- Java 1.4
Assumes JDK 27; sort and binarySearch read the same at JDK 25. List.sort, which Collections.sort delegates to, dates from Java 8.
context
- Collections (Java SE 27 & JDK 27)docs.oracle.com
- List (Java SE 27 & JDK 27)docs.oracle.com
- RandomAccess (Java SE 27 & JDK 27)docs.oracle.com