skip to content

How do Collections.sort and Collections.binarySearch work, and what are their requirements and complexity?

level: middleimportance: must knowfreq 65%

answer

  1. sort = in-place, n log n, stable (TimSort)
  2. natural order needs Comparable, else pass Comparator
  3. binarySearch requires a pre-sorted list
  4. not found => -(insertion point) - 1
  5. slow on LinkedList (no RandomAccess)

basics

~10 s

Collections.sort(list) orders a list ascending, either by the elements' natural order or by a Comparator you pass. Collections.binarySearch(list, key) finds an element quickly, but only works if the list is already sorted.

solid answer

~40 s

Collections.sort sorts a List in place. The no-comparator version requires elements to implement Comparable (natural ordering); the two-arg version takes a Comparator. It is a stable, n log n merge/TimSort. Collections.binarySearch performs a binary search and runs in log n time, but it 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 its index; if not, it returns (-(insertion point) - 1), a negative value encoding where the key would go. A subtle performance note: binarySearch on a LinkedList degrades to linear traversal cost because random access by index is O(n), so it is really only fast on RandomAccess lists like ArrayList.

code

java · 8 lines
java
List<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

for a junior

Can call Collections.sort and knows binarySearch needs a sorted list; knows sort mutates the list.

for a middle

Explains Comparable vs Comparator, the stable n log n cost, and decodes the negative not-found return value.

for a senior

Discusses TimSort, the RandomAccess/LinkedList performance trap, and prefers list.sort over Collections.sort in modern code.

for a principal

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**. This requires every element to implement `Comparable<T>`, i.e. to have a `compareTo` method. `String`, `Integer`, `LocalDate`, etc. already do. If they don't, you get a `ClassCastException` at runtime. - `Collections.sort(List<T>, Comparator<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. **Algorithm and complexity.** Modern Java sorts objects with **TimSort**, an adaptive, *stable* merge sort. *Stable* means equal elements keep their original relative order — important when sorting by one field after another. Time complexity is **O(n log n)** worst case; it is faster (near O(n)) on already-mostly-sorted data. Note that since Java 8 you can also call `list.sort(comparator)` directly (a default method on `List`); `Collections.sort` simply delegates to it now. ## 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 result is **undefined** (it won't throw — it just returns a meaningless value). This is the single most important fact about it. - **Found:** returns the **index** of the matching element. - **Not found:** returns `-(insertion point) - 1`. The *insertion point* is the index where the key would be inserted to keep the list sorted. This negative encoding lets you do both lookup and "where would it go" in one call. To turn a not-found result into an insertion index, compute `int insertAt = -result - 1;`. **Complexity:** **O(log n)** comparisons. But there is a trap: binary search jumps to the middle index, the middle of *that*, etc. Index access is O(1) on an `ArrayList` (which implements `RandomAccess`) but O(n) on a `LinkedList`. So binarySearch on a `LinkedList` does O(log n) *comparisons* but O(n) total *work* — 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 O(1) 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?
    It uses TimSort, a stable merge sort. Stability matters when chaining sorts — e.g. sort by name then by age keeps name-order within equal ages.

saying these in an interview costs you the question

  • Calling binarySearch on an unsorted list and trusting the result
  • Thinking binarySearch returns -1 when not found (it returns an encoded negative)
  • Assuming sort returns a new list
  • Believing binarySearch is O(log n) work on a LinkedList

context

resolving links…