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.

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!

The problem with saying: Sorting is O(n logn) is that this is an incomplete and therefore nebulous, undefined statement. It is unclear what it means. The problem is: You have failed to define what n is.

Now, in practice, n is usually obvious from context. For example, If I say: "Sorting an array of integers is O(n logn) assuming an optimal sorting algorithm", just about everybody who hears this will immediately realize that, whilst I didn't explicitly say what n is, clearly I mean: n = the number of ints in that array.

So let's go back to your problem: Now n is no longer clear.

Is n the # of strings in the array? Is n the average # of characters for all strings in that array?

We're really talking about 2 separate variables here. So, to properly describe the performance characteristics in terms of big-O notation for this problem, you'd say something like:

• Given: String[] str, for example: str = {"Hello", "World", "John", "Doe"}
• Let n be the number of elements in the str array.
• Let m be the average # of characters for the strings in the str array
• Then, calling Arrays.sort(str) on this array would have the performance characteristic of O(m * n log n).

The reason it's O(m*n logn) is because the sorting algorithm itself will run O(n logn) comparison operations in order to perform the sort. And each comparison operation takes O(m) time to finish, though that is very much the worst case scenario: Given, say, Hello and World, even though m = 5 for those two, the comparison completes after only 1 step; the algorithm compares H and W and answers immediately, never even looking at ello or orld. But if the strings are Hello1, Hello2, Hello3 and Hello4, then that's a guaranteed 5 'steps' for every time 2 strings are compared, and there will be ~n logn) comparisons. big-O is 'worst case scenario' (vs little o), hence, the algorithm is O(m*n log n).

Even though 'everybody says' O(n log n). Contex is important.

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.

An array that is already sorted is often, but not necessarily, the best case for a given sorting algorithm. For instance, if you choose your pivot point properly, a sorted array could actually be the worst case for quicksort.