How to compare running time between sorting methods quicksort and mergesort properly?

Question

I have an assignment to compare the execution times for sorting large arrays of integers with mergesort and quicksort. The implementations of the algorithms are copied from a book. They both sort integers in ascending order. I am then asked to state how much faster quicksort is on average. However, with my (albeit small) sample size of tests, I found that mergesort was quicker by a small %, which leads me to believe i'm testing improperly.

I have 2 programs, one for mergesort and one for quicksort. Their main() code is the same (shown below). I create an array of random size between 0 and some chosen upper limit. Then I fill the array with random integers. Then I sort the array and print it. I use the currentTimeMillis() to check the runtime of the programs. I do tests of 10 runs for quicksort and mergesort, add the total time and divide by 10 to get the average running time for the sorts. I did not find that quicksort was faster than mergesort on average. I've also tried using a fixed array size, but the results still do not hint at quicksort being faster. What would be a -proper- way to test?

public static void main(String[] args){
        /* create an array of some size 0 to 100000 with
           random integers and measure the time it takes
           to sort the array in ascending order (where sort() is either quicksort 
           or mergesort.)
        */
        long a = System.currentTimeMillis();
        Random rnd = new Random(System.currentTimeMillis());
        Integer[] array = new Integer[rnd.nextInt(100000)];
        for(int i = 0; i < array.length; i++){
            array[i] = rnd.nextInt();
        }
        sort(array);
        System.out.println(Arrays.toString(array));
        long b = System.currentTimeMillis() - a;
        System.out.println("Program runtime: " + b + "ms");
    }
}

Expected result: Quicksort average running time should be some % faster
in comparison to mergesort, for large random integer arrays.

Actual result: Mergesort was slightly faster in most tests 
(10K elements, 100K elements, 1000K elements).

while picking random elements is fine, I wouldn't say so about picking random sizes for arrays — mangusta, Sep 22 '19 at 14:19
Show us your code where you implemented both sorting algorithms. — mentallurg, Sep 22 '19 at 14:26

asynts · Accepted Answer · 2019-09-22T15:11:06.783

1

Your measurements include the generation of the random arrays, that's a heavy operation and will distort the result.

// do initialization here

long a = System.nanoTime();
sort(array);
long b = System.nanoTime();

// do the output here

... will only measure the time that passed during the execution of sort(array). Which is the time you are interested in.

Replacing System.currentTimeMillis() with System.nanoTime() makes the result more accurate.

edited Sep 22 '19 at 15:11

answered Sep 22 '19 at 15:00

asynts

2,213
2
21
35

Along with mangusta's answer of not picking random sizes of arrays, and excluding the array generation as part of the timing, I seem to be getting significant results now, where quicksort does indeed run faster. It turned out that array generation stood for more than 80% of the program runtime. – 0jnats3 Sep 22 '19 at 15:40

How to compare running time between sorting methods quicksort and mergesort properly?

1 Answers1