Insertion Sort - Performance

This section provides a tutorial on how to measure the performance of the Insertion Sort algorithm. My first Java implementation of Insert Sort is performing at the O(N*N) order level.

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

```Array size: 10000
Average sorting time: 55 milliseconds
Number of tests: 1000
Performance: 5.5 O(N) microseconds
Performance: 0.4139162440379741 O(N*Log2(N)) microseconds
Performance: 5.5E-4 O(N*N) microseconds

Array size: 20000
Average sorting time: 265 milliseconds
Number of tests: 1000
Performance: 13.25 O(N) microseconds
Performance: 0.9273702918995789 O(N*Log2(N)) microseconds
Performance: 6.625E-4 O(N*N) microseconds

Array size: 30000
Average sorting time: 641 milliseconds
Number of tests: 1000
Performance: 21.366666666666667 O(N) microseconds
Performance: 1.436639127707329 O(N*Log2(N)) microseconds
Performance: 7.122222222222223E-4 O(N*N) microseconds
```

The results showed us that the performance of insertion method is O(N*N), because the last performance line gave me a constant, when I increased the array size.

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

```Array size: 1000
Average sorting time: 21 milliseconds
Number of tests: 1000
Performance: 21.0 O(N) microseconds
Performance: 2.1072099696478683 O(N*Log2(N)) microseconds
Performance: 0.021 O(N*N) microseconds

Array size: 2000
Average sorting time: 83 milliseconds
Number of tests: 1000
Performance: 41.5 O(N) microseconds
Performance: 3.784499031049363 O(N*Log2(N)) microseconds
Performance: 0.02075 O(N*N) microseconds

Array size: 3000
Average sorting time: 191 milliseconds
Number of tests: 1000
Performance: 63.666666666666664 O(N) microseconds
Performance: 5.511909130172683 O(N*Log2(N)) microseconds
Performance: 0.021222222222222222 O(N*N) microseconds
```

Table of Contents