EigenFunk's blog

Java: Arrays.sort(a); Size matters?
By EigenFunk, history, 5 years ago, In English

Solving 977C - Less or Equal I stumbled over a TLE:

Submission: 80761653

After digging into this I found out that the code gets accepted if the array is expanded by just one element.

Submission: 80762181

Ok, so when sorting an array the time needed for sorting obviously depends on the size of the array, but I'm really surprised to see that increasing the size by one might make the difference between '218ms' or TLE.

I did some local tests, there are some variations but not that significant.

So maybe a layer 8 problem? Am I missing something?

Edit: Not surprising others have written about this in more detail:

Even here by Flatfoot

I think I knew that sorting algorithms have best- and worst-case behaviors. It's just that I'm still blown away that corner cases are so close to 'average' behavior. And still I don't see a pattern which would have signaled this.

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

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Just shuffle the array before sorting. That'd remove "TLE" if your logic is correct.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Not a Java programmer, but have heard multiple times that Arrays.sort() uses Quicksort, which works in $$$O(n^2)$$$ time in the worst case. Looking at test 6, it seems that it was specifically designed to hack Java's Quicksort.

As the performance of Quicksort largely depends on the initial order of the elements, just shuffle the array before sorting, as has been previously said.

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

    Note that the C++ std::sort is usually quicksort but it's a variation that runs in $$$O(n \log n)$$$ in the worst case.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Or you can use object array like Integer[] arr = new Integer[] I heard that object array uses TimSort which is NlogN in Average.

Primitive array uses quick sort which is O(n^2) in worst case.

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

Forget about Java: Arrays.sort(a); Answer to your second question. Does Size matters? Not initially. but yeah after few year. xD

For the first question, To be exact, Java uses Dual Pivot Quick Sort. You should always avoid Arrays.sort(a) or try shuffling array before using it.

→ Reply