Timing an insertion sort of different lenghts with System.nanoTime()

Question

I have some code, in Java, to time the average of 10 tries of an insertion sort. It sorts the same array but up to 100 words, 200 words etc. up until the full lenght of on array. The code below is for 100 and 200 words respectively but it all looks the same with just the variables changed.

However every next average time seems to get shorter and shorter. Eg. 9658233ns for 100 words, 4273459ns for 200 words, 3716726ns for 300 words, 2965091ns for 400 words and 2842528ns for 459 words. However if I inverse the order, sorting through whole array first and array of 100 words last, it takes the longest amount of time to sort through the full array and shortest amount of time to sort through the array of 100 words.

Would using a different way to time the insertion sort lead me to more consistent results?

    long i1AverageTime = 0L;
    for (int i = 0; i < 10; i++) {
        long start = System.nanoTime();
        insertionSort(myArray, 100);
        long end = System.nanoTime();
        long timeTaken = end - start;
        i1AverageTime += timeTaken;
    }
    i1AverageTime /= 10;

    long i2AverageTime = 0L;
    for (int i = 0; i < 10; i++) {
        long start = System.nanoTime();
        insertionSort(myArray, 200);
        long end = System.nanoTime();
        long timeTaken = end - start;
        i2AverageTime += timeTaken;
    }
    i2AverageTime /= 10;

See the Microbenchmark Suite [built into Java 12](https://openjdk.java.net/jeps/230). — Basil Bourque, May 08 '19 at 01:39

artemis · Answer 1 · 2019-05-08T00:05:36.403

Using timing methods for algorithm analysis is really a difficult way to judge algorithm performance, especially on a laptop or a machine for personal or school use.

There are a number of reasons you might be getting erratic times:

Your computer's processing speeds are likely changing every second you run. Things like web browsers, antivirus, and other background processes are affecting how much processing power you have and therefore affecting your ability to run the algorithms.
The same holds true for memory. Your RAM usage and memory availability is constantly changing and is very volatile, so using it to measure performance is not a safe metric.

A more accurate way to measure the performance of your algorithm would be to analyze the run-time complexity of your algorithm against its known complexity (normally O(n) or O(n^2)).

Timing an insertion sort of different lenghts with System.nanoTime()

1 Answers1