Arrays.sort(int[])
As well as Arrays.sort(long[]), Arrays.sort(float[]) and Arrays.sort(double[])
Time complexity
Time complexity of Arrays.sort(int[])
depends on the version of Java.
O(n2) prior to Java 14
A pretty ordinary quicksort was used with time complexity ranging from O(n) (when the array is already sorted and we are only checking that it is) to O(n2) for certain inputs that cause extremely uneven distribution of elements into parts with an average complexity of O(n log(n)). You can find a detailed analysis here.
O(n log(n)) starting from Java 14
In Java 14 the implementation was improved to guarantee the worst-case time complexity of O(n log(n)). The function was changed to resort to heapsort if recursion becomes too deep:
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
heapSort(a, low, high);
return;
}
which prevents the method from degrading to quadratic time complexity.
Glimpse into the future
There is an initiative to switch to radix sort for almost random big enough arrays thus reducing the time complexity to O(n) in the worst-case.
O(n) space
In all versions, the algorithm has space complexity ranging from O(1) (when the array is already sorted and we only to check that it is) to O(n) (when the array is highly structured (there is a small number of sorted subarrays inside the original array and we merge those subarrays)).
Here's where allocation happens in the worst case:
/*
* Merge runs of highly structured array.
*/
if (count > 1) {
int[] b; int offset = low;
if (sorter == null || (b = (int[]) sorter.b) == null) {
b = new int[size];
} else {
offset = sorter.offset;
}
mergeRuns(a, b, offset, 1, sorter != null, run, 0, count);
}
return true;
DualPivotQuicksort.java
While the question asks specifically about Arrays.sort(int[]) method I still decided to include answers for other data types since this is the first result when you look for Arrays.sort() time and space complexity in Google and it is not easy to find correct answers to this simple question in other places.
Arrays.sort(short[])
As well as Arrays.sort(char[]) and Arrays.sort(byte[])
O(n) time, O(1) space
Although the documentation says:
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 all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations.
This is not true at least starting from Java 7. Actually, an in-place counting sort used for big enough arrays, which has linear time complexity and constant space complexity:
private static void countingSort(short[] a, int low, int high) {
int[] count = new int[NUM_SHORT_VALUES];
/*
* Compute a histogram with the number of each values.
*/
for (int i = high; i > low; ++count[a[--i] & 0xFFFF]);
/*
* Place values on their final positions.
*/
if (high - low > NUM_SHORT_VALUES) {
for (int i = MAX_SHORT_INDEX; --i > Short.MAX_VALUE; ) {
int value = i & 0xFFFF;
for (low = high - count[value]; high > low;
a[--high] = (short) value
);
}
} else {
for (int i = MAX_SHORT_INDEX; high > low; ) {
while (count[--i & 0xFFFF] == 0);
int value = i & 0xFFFF;
int c = count[value];
do {
a[--high] = (short) value;
} while (--c > 0);
}
}
}
Counting sort implementation
Arrays.sort(Object[])
Unlike other methods, this one is well-documented and the documentation here corresponds to reality.
O(n log(n)) time
Starting from Java 7
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.
https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])
Before Java 7
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.
https://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(java.lang.Object[])
O(n) space
Starting from Java 7
Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.
https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])
Before Java 7
The algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort to sort object references 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)." It is a reasonably fast stable sort that guarantees O(n log n) performance and requires O(n) extra space.
https://bugs.openjdk.org/browse/JDK-6804124
Arrays.sort()
to employ some magic, I think the question about what minimum time complexity it has is quite answerable, isn't it?Arrays.sort
, so whichever algorithm that uses. It's hard to tell what language this is (guessing Java), but standard library sorts are almost always comparison sorts.Arrays.sort
's time and space complexity?", which is really a question which shows no research effort, as this is fairly well-documented.