Which sorting algorithm is used internally in collections sort method?

Question

In collections class have a method sort() using for sort the collection elements, but I have one doubt, internally which sorting algorithm is used to sort the elements. I googled it but not got correct answer. help me please .

Answer 1

The answer depends on the implementation of Java that you are talking about, and the type of data structure you are sorting.

For example, the javadoc for Collections (in Java 6) states:

Implementors should feel free to substitute other algorithms, so long as the specification itself is adhered to. (For example, the algorithm used by sort does not have to be a mergesort, but it does have to be stable.)

Having said that, the javadocs for different versions say this about the Collections::sort methods:

Java 6:

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

For sorting "native arrays" (ex: ints) it uses a "quicksort" that defaults to insertion sort for small chunks/array sizes.

Java 7:

Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techiques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

For sorting "native arrays" (ex: ints) it uses a "dual pivot quicksort."

Java 8:

The Collections javadoc defers to List::sort which says the same thing as the Java 7 text quoted above. Java 8's "dual pivot quicksort" had a few minor enhancements, apparently.

Java 9:

No change

Java 10:

More enhancement's have been proposed for dual pivot quicksort.

---

Also note that things may be different for other sort APIs; e.g. those in the Arrays class that are tailored for arrays of primitives. For example Java 9 / Arrays::sort(int[]) says:

Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

And the parallelSort methods are different again.

---

The bottom line is that if you want to be sure which algorithm is used, look at the source code for the version of Java that you are using.

Answer 2

According to documentation (emphasis mine):

Implementation note: This implementation is a stable, adaptive, iterative mergesort ...