Search Algorithm in Java Collection

Question

This question might have been answered. I couldn't find it though.

In Java Collections i have always used Collections.sort(coll) followed by search. My question is that will collections always perform binary search or is it decided internally. Does collection store any identifier to decide between linear and binary search.

Answer 1

When you look at the Java 8 source code of Collections.sort(coll), it uses the Arrays.sort(Object[] a) method. If you do not pass java.util.Arrays.useLegacyMergeSort as a system property. Otherwise, it uses legacy merge sort.

Arrays.sort(Object[] a) uses TimSort which is strategic algorithm that chooses insertion sort or merge sort according to the given array's ordering and size. You can find the details in below links:

• https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-java.lang.Object:A-
• https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399