Collections - Beginning Java 8 Language Features - page 579

The sort() method uses a modified mergesort algorithm. It is a stable sort. That is, equal elements will stay at
their current positions after the sort operation. Internally, all elements are copied to an array, sorted in the array, and
copied back to the List . Sorting is guaranteed to give n*log(n) performance, where n is the number of elements in
the List .

Searching a List
You can use one of the following two static binarySearch() method in the Collections class to search for a key in
a List .

<T> int binarySearch(List<? extends Comparable<? super T>>list, T key) •

<T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
A List must be sorted in ascending order using the natural order or the Comparator object before you use the
binarySearch() method on the List . If the List is not sorted, the result of the binarySearch() method is not defined.
If the key is found in the List , the method returns the index of the key in the List . Otherwise, it returns ( -(insertion
index) -1 ), where the insertion index is the index in the List where this key would have been placed, if it were present.
This return value makes sure that you will get a negative value only if the key is not found in the List . If you get a
negative number as the retuned value from this method, you can use the absolute value of the return index as the basis
of the insertion point into the list -((return value) + 1) . This method uses the binary search algorithm to perform
the search. If the List supports random access, the search runs in log(n) time. If the List does not support random
access, the search runs in n×log(n) time. The following snippet of code shows how to use this method:

•

List<String> list = new ArrayList<>();
list.add("John");
list.add("Richard");
list.add("Donna");
list.add("Ken");

// Must sort before performing the binary search
Collections.sort(list);
System.out.println("List: " + list);

// Find Donna
int index = Collections.binarySearch(list, "Donna");
System.out.println("Donna in List is at " + index);

// Find Ellen
index = Collections.binarySearch(list, "Ellen");
System.out.println("Ellen in List is at " + index);

List: [Donna, John, Ken, Richard]
Donna in List is at 0
Ellen in List is at -2

Since "Ellen" is not in the List , the binary search returned -2. It means that if you insert "Ellen" in the List , it
will be inserted at index 1, which is computed using the expression (-(-2+1) ). Note that “ Donna ” has an index of 0 and
"John" has an index of 1. If “ Ellen ” is added to the list, its index will be the same as the current index for "John" and
"John" will be moved to the right at index 2.