The Running Time For Arrays.Sort Method in Java

Question

Does anyone know the running time in big O notation for the arrays.sort java method? I need this for my science fair project.

Answer 1

From official docs

I've observed that there are primarily two approaches. So, it depends on what you are sorting and what overloaded method from sort family of methods you are calling.

Docs mention that for primitive types such as long, byte (Ex: static void sort(long[])):

The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

For Object types: (Ex: void sort(Object list[]))

Guaranteed O(nlogn) performance

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.

Hope that helps!

Answer 2

Arrays.sort() uses Tim sort - O(N log N) for array of objects and QuickSort for arrays of primitives - again O(N log N).

Here is an awesome comparison of sorting algorithms: http://www.sorting-algorithms.com/