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

Question

There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1).

If I use Arrays.sort(arr), and use a for loop to one pass loop, for example:

public static int hello(int[]A){   Arrays.sort(A);   for(int i=0;i<A.length;i++){      ....................   }   return ....; 

}

So the loop will cost O(n) time. My question is: will Arrays.sort() cost more time? If I use Arrays.sort(), will this time complexity still be O(n)? And will Arrays.sort() cost more space?

Answer 1

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?

Yes, Arrays.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 Ω(n²) 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:

• http://en.wikipedia.org/wiki/Counting_sort
• http://en.wikipedia.org/wiki/Pigeonhole_sort
• http://en.wikipedia.org/wiki/Radix_sort

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.

Answer 2

According to the java jvm 8 javadocs of Arrays.sort() method:

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 many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

So it will increase your time complexity from O(n) to O(n log(n))