0

I've been working on a 3-way merge sort algorithm, and the professor wants me to average how much time it takes to merge sort an array of 1000, 10000, 100000, 1000000 and 10000000 randomized integers over 10 trials each. However, I've been facing a problem while trying to calculate the run time; for example, when I calculate the run time for 1 million elements it displays that it took around 300ms while in reality it's taking around 40 seconds. I'm going to leave the code of my main function, I also tried putting startTime at the start and it would display the same running time.

public static void main(String args[]) {
    Random r = new Random();

    int[] arr = new int[1000000];
    for (int i = 0; i < arr.length; i++)
        arr[i] = r.nextInt();

    long startTime = System.currentTimeMillis();
    MergeSort test = new MergeSort(); 
    test.sort(arr, 0, arr.length); 
    
    long endTime = System.currentTimeMillis();
    long timeElapsed = endTime - startTime;
    print(arr);
    System.out.println("Execution time in milliseconds: " + timeElapsed);
}
0009laH
  • 1,960
  • 13
  • 27
Ali Hashem
  • 23
  • 4
  • I think I read somewhere that benchmarking java applications isn't quite as easy and reliable. Maybe see [this](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java/513259). You could try to use `System.nanoTime()` instead of `System.currentTimeMillis()`. Maybe this will give you more accurate results. – maloomeister Sep 30 '20 at 10:28
  • Also, maybe it is also interesting to see how long the population of the array with the random numbers will take. You could add another measurement there to see where the time is spent. Using the Java 8 Stream API may also be faster populating the array. E.g. something like `int[] array = new Random().ints(size, lowBound, highBound).toArray();` – maloomeister Sep 30 '20 at 10:29
  • 1
    Additionally, printing an array of 1000000 might take some time as well (not 40 sec though) – Loïc Sep 30 '20 at 10:36
  • **Tip:** Either your `MergeSort test` variable should be a singleton, or you should make `MergeSort.sort` static. If `sort` is an interface method on a `Sorter` interface, then make `test` a singleton. I see no need in instantiating it more than once. Do this, if you need to performance test multiple arrays within a loop. – Mr. Polywhirl Sep 30 '20 at 15:52
  • How do you know that "in reality it's taking around 40 seconds"? What you measure by the wall clock is not just sorting, but initialization+sorting+printing, and apparently printing is the most time consuming part. Try to comment out `print(arr);` – apangin Sep 30 '20 at 21:07

0 Answers0