I am using JDK-8 (x64). For
Arrays.sort (primitives) I found the following in the Java documentation:
The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch.`
Collections.sort (objects) I found this “Timsort”:
This implementation is a stable, adaptive, iterative mergesort … 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.
Collections.sort uses an array, why doesn’t it just call
Arrays.sort or use dual-pivot QuickSort? Why use Mergesort?
The API guarantees a stable sorting which Quicksort doesnât offer. However, when sorting primitive values by their natural order you wonât notice a difference as primitive values have no identity. Therefore, Quicksort can used for primitive arrays and will be used when it is considered more efficientÂ¹.
For objects you may notice, when objects with different identity which are deemed equal according to their
equals implementation or the provided
Comparator change their order. Therefore, Quicksort is not an option. So a variant of MergeSort is used, the current Java versions use TimSort. This applies to both,
Collections.sort, though with JavaÂ 8, the
List itself may override the sort algorithms.
Â¹ The efficiency advantage of Quicksort is needing less memory when done in-place. But it has a dramatic worst case performance and canât exploit runs of pre-sorted data in an array, which TimSort does.
Therefore, the sorting algorithms were reworked from version to version, while staying in the now-misleadingly named class
DualPivotQuicksort. Also, the documentation didnât catch up, which shows, that it is a bad idea in general, to name an internally used algorithm in a specification, when not necessary.
The current situation (including JavaÂ 8 to Java 11) is as follows:
- Generally, the sorting methods for primitive arrays will use Quicksort only under certain circumstances. For larger arrays, they will try to identify runs of pre-sorted data first, like TimSort does, and will merge them when the number of runs does not exceed a certain threshold. Otherwise they will fall back to Quicksort, but with an implementation that will fall back to Insertion sort for small ranges, which does not only affect small arrays, but also quick sortâs recursion.
sort(short,â¦)add another special case, to use Counting sort for arrays whose length exceeds a certain threshold
sort(byte,â¦)will use Counting sort, but with a much smaller threshold, which creates the biggest contrast to the documentation, as
sort(byte,â¦)never uses Quicksort. It only uses Insertion sort for small arrays and Counting sort otherwise.