What is the worst case time complexity of Java 14+ Arrays.sort( int[] )?

user_2763256 0
Viewed 103

While I know this seems obvious I'll explain my confusion. I've always thought of Quicksort's worst case time complexity as O(n^2). The documentation for Arrays.sort(int[]) from Java 7 to Java 13 says: 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.

The keyword here is "many", so I assume O(n log(n)) here refers to the average case, and there still exists data sets that result in a worst case of O(n^2).

But in Java 14 and up, the documentation for Arrays.sort(int[]) says: This algorithm offers O(n log(n)) performance on all data sets.

So is the worst case for this improved implementation of Quicksort now O(n log(n)) ? Someone please clarify.

java-14 quicksort time-complexity algorithm java
1 Answers

You need to check deeper implementation of Arrays.sort(int[]).

Inside there is a function DualPivotQuicksort.sort(...) which is used for sorting.

You can see in java 7 to 13 that function have a fail safe mechanism which changes sorting type if complexity is near O(n^2), it's changing to QuickSort which average complexity is O(n log n) but it's worst is O(n^2) that's why in javaDoc description says "many data sets".

On the other hand since java 14 fail safe for higher complexity is changing sort algorithm to heapsort which have worst complexity of O(n log n) so it never will be slower than that.

user_74063380
Related