Quicksort or O(N.logN) sort in jdk

Question

Is there a quicksort, or another O(N.logN) sort, available in the jdk standard library?

Collections class doesn't bring hope:

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.)

and Collections.sort() gives no clue:

sort(List<T> list) Sorts the specified list into ascending order,according to the natural ordering of its elements.

Check http://stackoverflow.com/questions/753237/what-sort-does-java-collections-sortnodes-use — Jonathan Drapeau, Mar 11 '13 at 12:26
@JonathanDrapeau thanks for pointing that out, I remember reading about the Timsort but had forgotten about it: http://en.wikipedia.org/wiki/Timsort, always impressive to see such innovations pop up in recent years (2002) — Christophe Roussy, Mar 11 '13 at 12:50

score 2 · Answer 1 · answered Mar 11 '13 at 12:31

2

Collections.sort is an optimized merge sort which actually guarantees O(n log n) in every case and it is stable; link .

answered Mar 11 '13 at 12:31

Random42

8,989
6
55
86

score 1 · Accepted Answer · edited May 23 '17 at 12:04

Sorting relies on Arrays.sort. As the sort method depends on the type, reading the JavaDoc is not so obvious. A modified merge sort or a tuned quicksort depending on a threshold:

 /**
 * Tuning parameter: list size at or below which insertion sort will be
 * used in preference to mergesort or quicksort.
 */
private static final int INSERTIONSORT_THRESHOLD = 7;

Here is a post comparing quicksort and mergesort: Quick Sort Vs Merge Sort

Conclusion: trust the Java implementation unless you really know what you are doing.

Quicksort or O(N.logN) sort in jdk

2 Answers2