Merge Sort - Performance

Sorting Algorithm Tutorials - Herong's Tutorial Examples

∟Merge Sort Algorithm and Java Implementation

∟Merge Sort - Performance

This section provides a tutorial on how to measure the performance of the Merge Sort algorithm. My first Java implementation of Merge Sort is performing somewhere between O(N*Log2(N) and O(N*N) order levels.

Now let's see how my Java implementation of the Merge Sort algorithm performs. Here are the results with my SortTest.java class and HyArrays.mergeSort() function using JDK 13.

Array size: 100000
Average sorting time: 19 milliseconds
Number of tests: 1000
Performance: 0.19 O(N) microseconds
Performance: 0.011439139835231284 O(N*Log2(N)) microseconds
Performance: 1.9E-6 O(N*N) microseconds

Array size: 200000
Average sorting time: 59 milliseconds
Number of tests: 1000
Performance: 0.295 O(N) microseconds
Performance: 0.0167521875547794 O(N*Log2(N)) microseconds
Performance: 1.475E-6 O(N*N) microseconds

Array size: 300000
Average sorting time: 109 milliseconds
Number of tests: 1000
Performance: 0.36333333333333334 O(N) microseconds
Performance: 0.019969291653651973 O(N*Log2(N)) microseconds
Performance: 1.2111111111111111E-6 O(N*N) microseconds

The performance of this implementation is at the order of O(N*Log2(N)).

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

Array size: 10000
Average sorting time: 98 milliseconds
Number of tests: 1000
Performance: 9.8 O(N) microseconds
Performance: 0.7375234893767539 O(N*Log2(N)) microseconds
Performance: 9.8E-4 O(N*N) microseconds

Array size: 20000
Average sorting time: 222 milliseconds
Number of tests: 1000
Performance: 11.1 O(N) microseconds
Performance: 0.7768913388743642 O(N*Log2(N)) microseconds
Performance: 5.55E-4 O(N*N) microseconds

Array size: 30000
Average sorting time: 336 milliseconds
Number of tests: 1000
Performance: 11.2 O(N) microseconds
Performance: 0.753058887534575 O(N*Log2(N)) microseconds
Performance: 3.733333333333333E-4 O(N*N) microseconds