CazadorDivino's blog

Sort array of int vs Sort array of Integer
By CazadorDivino, 9 years ago, In English

Why Arrays.sort(Integer) is more fast that Arrays.sort(int) ?(JAVA)

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Because of antiquicksort tests. You can random-shuffle your array before sorting and everything will be fine

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

    As I can do random-shuffle, could you tell me more about what it means to do that. Because as I understand it has to do with the algorithms using JAVA to order according to data type.

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

      Let's say that you are given a random permutation of ints from 1, 2, ..., n. If you sort them with Arrays.sort then you are almost completely sure that it will be , that means that the probability of hitting a permutation that causes O(n2) is so low that is negligible. Furthermore, it will be faster than using a Mergesort (because Quicksort is almost always faster than Mergesort).

      However, if the input is not a random permutation, then whoever made that input could have been "malicious" and tuned the order of the numbers in order to cause O(n2) behavior. If you use random shuffle, then you're back in the case no matter what original order the input had.

      See dalex's post if you want to see how to generate a "malicious" input.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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(n2) worst case. Instead, in the Arrays.sort(Object) case, it uses Mergesort, which has a worst case.

Why? Check out the answer here.

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

on average sample, sort(int) is much faster (because it works with primitives), but it has O(N^2) worstcase because it's plain quicksort, and in certain CF problems other users might use it to hack solution. sort(Integer) is mergesort and while it's slower, its worstcase is still O(N*log N)

→ Reply