Java: Arrays.sort(Integer) is more faster than Arrays.sort(int) in the worst case:

The main reason is that Java uses two different sorting algorithms in the cases you mentioned. In the Arrays.sort(int) (or other primitive types) case, Java uses Quicksort, which has a O(n^2) worst case. Instead, in the Arrays.sort(Object) case, it uses Mergesort, which has a O(n log n) worst case.

So some problems may give you Time Limit Exceeded when you use Arrays.sort(int) if there is an anti-quicksort test.

References:

http://mirror.codeforces.com/blog/entry/17565

http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types

Example 1:

Time limit exceeded because of Arrays.sort(int)

http://mirror.codeforces.com/contest/285/submission/20103799

Same code but Accepted because of Arrays.sort(Integer)

http://mirror.codeforces.com/contest/285/submission/20103803

Example 2:

Time limit exceeded on test 46 ( because of Arrays.sort(int) )

http://mirror.codeforces.com/contest/433/submission/20104326

Accepted after changing it to Arrays.sort(Integer)

http://mirror.codeforces.com/contest/433/submission/20104369

When does the worst case of Quicksort occur?

http://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/

But why is Quicksort more popular than Mergesort ?

1)Is in-place (MergeSort requires extra memory linear to number of elements to be sorted).

2)Has a small hidden constant.

Reference:

http://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort