Will Arrays.sort() increase time complexity and space time complexity?

I am assuming you are talking about Java here.

So the loop will cost O(n) time, my question is that will Arrays.sort() cost more time?

YesArrays.sort(int[]) in all Java standard library implementations that I know, is an example of a comparison-based sort and thus must have worst-case complexity Ω(n log n). In particular, Oracle Java 7 uses a dual-pivot quicksort variant for the integer overloads, which actually has an Ω(n2) worst case.

and will Arrays.sort() cost more space?

In all likelihood it will use ω(1) space (which means another yes, the space usage is not O(1)). While it’s not impossible to implement a comparison-based sort with only constant extra space, it’s highly impractical.

That said, under certain conditions it is possible to sort specific types of data in linear time, see for example:

With a constant range of input integers (for example if abs(A[i]) <= C for some constant C), then counting sort and radix sort use indeed only O(n) time and O(1) space, so that might be useful.

Leave a Comment