tuna's blog

Java: Arrays.sort(Integer) vs Arrays.sort(int) with Examples
By tuna, history, 8 years ago, In English

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://codeforces.net/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://codeforces.net/contest/285/submission/20103799

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

http://codeforces.net/contest/285/submission/20103803

Example 2:

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

http://codeforces.net/contest/433/submission/20104326

Accepted after changing it to Arrays.sort(Integer)

http://codeforces.net/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

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I suggest O(n) optimization demonstrated below for time-constrained problems:

http://codeforces.net/contest/285/submission/20108766

Edit: my solution above is wrong as outputs mod n may colide (10^6 + 7 is not a prime).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can add to the blog that one can easily sort primitive datatypes and not get TLE, just by shuffling the array randomly.

I've been a victim so I know :P

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

My solution got hacked due to this today. Should've used Integer array

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    you can still use quick sort while avoiding get hacked. The idea is to randomize the order of the input and then use quick sort. This should work as the probability of the worst case would be nearly non existent.

    → Reply