You probably know that in order to sort array in Java you should use Arrays.sort. But do you know what algoritms are used inside?

If we open implementaion we’ll see that for primitive arrays Dual Pivot QSort is used. That’s a modified QSort that splits array into three peaces instead of two in QSort. While Time Sort is used for Objects which is an upgraded version of Merge Sort.

Let’s do some experiments and sort primitive array int[] and and array of objects Integer[]. Also let’s sort ArrayList<Integer> using Collections.sort.

 
    int n = 1000000;
    int[] ints = new int[n];
    Integer[] integers = new Integer[n];
    ArrayList<Integer> list = new ArrayList<>(n);

    for (int i = 0; i < n; ++i) {
        int val = (int)Math.round(Math.random() * Integer.MAX_VALUE);
        ints[i] = val;
        integers[i] = val;
        list.add(val);
    }

    long startTime = System.currentTimeMillis();
    Arrays.sort(ints);
    float estimatedTime = (System.currentTimeMillis() - startTime) / 1000f;
    System.out.printf("int[] is sorted for %.3f seconds\n\n", estimatedTime);

    startTime = System.currentTimeMillis();
    Arrays.sort(integers);
    estimatedTime = (System.currentTimeMillis() - startTime) / 1000f;
    System.out.printf("Integer[] is sorted for %.3f seconds\n\n", estimatedTime);

    startTime = System.currentTimeMillis();
    Collections.sort(list);
    estimatedTime = (System.currentTimeMillis() - startTime) / 1000f;
    System.out.printf("ArrayList<Integer> is sorted for %.3f seconds\n\n", estimatedTime);

The result is the following: int[] is sorted for 0.245 seconds

Integer[] is sorted for 0.813 seconds

ArrayList is sorted for 0.712 seconds

So what can we say:

  • int[] is sorted almost 4x faster than integer[]. QSort is faster than TimeSort especially without any comparator-specific code
  • Arrays.sort(int[]) has worst case O(n^2), that’s very slow, but in specific test case similar to antiqsort .
  • Collections.sort is also uses Time Sort b> with some arrays copying
  • Arrays.sort(object[]) is stable because Time Sort is stable. It means it doesn’t swap equal elements. It could be useful in real practice if you are sorting by priorities or something like that.

So my advice is the following:

  • Use Arrays.sort(int[]) as default solution except two following cases
  • If you must guarantee that your code works O(n log n) use Arrays.sort(Integer[])
  • If you are participating in programming contests (like codeforces.com) use Arrays.sort(Integer[]) because it often has antiqsort tests.

Stay tuned, check out my blog for more useful tips and tricks.