Time Comparison of Arrays.sort(Object[]) and Arrays.sort(int[])

1. Overview

In this quick tutorial, we’ll compare the two Arrays.sort(Object[]) and Arrays.sort(int[]) sorting operations.

First, we’ll describe each method separately. After that, we’ll write performance tests to measure their running times.

2. Arrays.sort(Object[])

Before we move ahead, it’s important to keep in mind that Arrays.sort() works for both primitive and reference type arrays.

Arrays.sort(Object[]) accepts reference types.

For example, we have an array of Integer objects:

Integer[] numbers = {5, 22, 10, 0};

To sort the array, we can simply use:

Arrays.sort(numbers);

Now, the numbers array has all its elements in ascending order:

[0, 5, 10, 22]

Arrays.sort(Object[]) is based on the TimSort algorithm, giving us a time complexity of O(n log(n)). In short, TimSort makes use of the Insertion sort and the MergeSort algorithms. However, it is still slower compared to other sorting algorithms like some of the QuickSort implementations.

3. Arrays.sort(int[])

On the other hand, Arrays.sort(int[]) works with primitive int arrays.

Similarly, we can define an int[] array of primitives:

int[] primitives = {5, 22, 10, 0};

And sort it with another implementation of Arrays.sort(int[]). This time, accepting an array of primitives:

Arrays.sort(primitives);

The result of this operation will be no different from the previous example. And the items in the primitives array will look like:

[0, 5, 10, 22]

Under the hood, it uses a Dual-Pivot Quicksort algorithm. Its internal implementation from the JDK 10 is typically faster than traditional one-pivot Quicksort.

This algorithm offers O(n log(n)) average time complexity. That’s a great average sorting time for many collections to have. Moreover, it has the advantage of being completely in place, so it does not require any additional storage.

Though, in the worst case, its time complexity is O(n²). 

4. Time Comparison

So, which algorithm is faster and why? Let’s first do some theory, and then we’ll run some concrete tests with JMH.

4.1. Qualitative Analysis

Arrays.sort(Object[]) is typically slower compared to Arrays.sort(int[]) for a few different reasons.

The first is the different algorithms. QuickSort is often faster than Timsort.

Second is how each method compares the values.

See, since Arrays.sort(Object[]) needs to compare one object against another, it needs to call each element’s compareTo method. At the very least, this requires a method lookup and pushing a call onto the stack in addition to whatever the comparison operation actually is.

On the other hand, Arrays.sort(int[]) can simply use primitive relational operators like < and >, which are single bytecode instructions.

4.2. JMH Parameters

Finally, let’s find out which sorting method runs faster with actual data. For that, we’ll use the JMH (Java Microbenchmark Harness) tool to write our benchmark tests.

So, we are just going to do a very simple benchmark here. It’s not comprehensive but will give us an idea of how we can approach comparing Arrays.sort(int[]) and Arrays.sort(Integer[]) sorting methods.

In our benchmark class we’ll use configuration annotations:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Measurement(batchSize = 100000, iterations = 10)
@Warmup(batchSize = 100000, iterations = 10)
public class ArraySortBenchmark {
}

Here, we want to measure the average time for a single operation (Mode.AverageTime) and display our results in milliseconds (TimeUnit.MILLISECONDS). Furthermore, with the batchSize parameter, we’re telling JMH to perform 100,000 iterations to make sure our results have high precision.

4.3. Benchmark Tests

Before running the tests, we need to define the data containers which we want to sort:

@State(Scope.Thread)
public static class Initialize {
    Integer[] numbers = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 
      1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, 
      -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167 };
    int[] primitives = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 
      1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, 
      -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167};
}

Let’s choose the Integer[] numbers and the int[] primitives array of primitive elements. The @State annotation indicates that the variables declared in the class won’t be the part of running benchmark tests. However, we can then use them in our benchmark methods.

Now, we’re ready to add the first micro-benchmark for Arrays.sort(Integer[]):

@Benchmark
public Integer[] benchmarkArraysIntegerSort(ArraySortBenchmark.Initialize state) {
    Arrays.sort(state.numbers);
    return state.numbers;
}

Next, for Arrays.sort(int[]):

@Benchmark
public int[] benchmarkArraysIntSort(ArraySortBenchmark.Initialize state) {
    Arrays.sort(state.primitives);
    return state.primitives;
}

4.4. Test Results

Finally, we run our tests and compare the results:

Benchmark                   Mode  Cnt  Score   Error  Units
benchmarkArraysIntSort      avgt   10  1.095 ± 0.022  ms/op
benchmarkArraysIntegerSort  avgt   10  3.858 ± 0.060  ms/op

From the results, we can see that Arrays.sort(int[]) method performed better than to Arrays.sort(Object[]) in our test, likely for the earlier reasons we identified.

And even though the numbers appear to support our theory, though we’d need to do testing with a greater variety of inputs to get a better idea.

Also, keep in mind that the numbers we present here are just JMH benchmark results – so we should always test in the scope of our own system and runtime.

4.5. Why Timsort Then?

We should probably ask ourselves a question, then. If QuickSort is faster, why not use it for both implementations?

See, QuickSort isn’t stable, so we can’t use it to sort Objects. Basically, if two ints are equal, it doesn’t matter that their relative order stays the same since one 2 is no different from another 2. With objects though, we can sort by one attribute and then another, making the starting order matter.

5. Conclusion

In this article, we compared two sorting methods available in Java: Arrays.sort(int[]) and Arrays.sort(Integer[]). Additionally, we discussed the sorting algorithms used in their implementations.

Finally, with the help of benchmark performance tests, we showed a sample run time of each sorting option.