java.util.Arrays.sort()

Sorting Algorithm Tutorials - Herong's Tutorial Examples

∟java.util.Arrays.sort() - Performance

This section provides a tutorial on how to measure the performance of the java.util.Arrays.sort() function provided by JDK.

Before implementing my own versions of different sorting algorithms, I used the test program, SortTest.java, to get some performance results with the java.util.Arrays.sort() function provided by JDK 13. Here are the results:

Array size: 100000
Average sorting time: 25 milliseconds
Number of tests: 1000
Performance: 0.25 O(N) microseconds
Performance: 0.015051499783199059 O(N*Log2(N)) microseconds
Performance: 2.5E-6 O(N*N) microseconds

Array size: 200000
Average sorting time: 66 milliseconds
Number of tests: 1000
Performance: 0.33 O(N) microseconds
Performance: 0.018739735230770178 O(N*Log2(N)) microseconds
Performance: 1.65E-6 O(N*N) microseconds

Array size: 300000
Average sorting time: 112 milliseconds
Number of tests: 1000
Performance: 0.37333333333333335 O(N) microseconds
Performance: 0.020518905185403863 O(N*Log2(N)) microseconds
Performance: 1.2444444444444445E-6 O(N*N) microseconds

The result was very impressive. I had to increase the array size to 100,000 to get the performance measurements. As you can see, the performance is close to the order of O(N*Log2(N)).

As a reference, results from an older computer with an older JDK version are listed below:

Array size: 10000
Average sorting time: 17 milliseconds
Number of tests: 1000
Performance: 1.7 O(N) microseconds
Performance: 0.127937748157192 O(N*Log2(N)) microseconds
Performance: 1.7E-4 O(N*N) microseconds

Array size: 20000
Average sorting time: 45 milliseconds
Number of tests: 1000
Performance: 2.25 O(N) microseconds
Performance: 0.1574779740961549 O(N*Log2(N)) microseconds
Performance: 1.125E-4 O(N*N) microseconds

Array size: 30000
Average sorting time: 70 milliseconds
Number of tests: 1000
Performance: 2.3333333333333335 O(N) microseconds
Performance: 0.15688726823636978 O(N*Log2(N)) microseconds
Performance: 7.777777777777778E-5 O(N*N) microseconds