CODEWITHSUNDEEP
javamemorymemory-managementquicksortmergesort
Motifier
Motifier

Reputation: 13

Why does order of mergesort and quicksort operations cause the second operation to run faster?

Using Java (if it matters)

I am running MergeSort and QuickSort one after the other and comparing the run times of both, on my computer when sorting 10,000,000 values I am finding that The run times when MergeSort is run then QuickSort

MergeSort = 1.6s (approx)

QuickSort = 0.3s (approx)

When running Quicksort first then MergeSort for the same input size of 10,000,000 I get

MergeSort = 0.6s

QuickSort = 1.2s

I'm assuming this might have something to do with Memory Allocation but I'm not sure how you would explain it

-EDIT- Before running both routines I am creating two seperate arrays a[ ] and b[ ] of a file randomintegers.dat which contains 10,000,000 random values. MergeSort sorts array a[ ], QuickSort sorts array b[ ]. (i.e. both arrays are seperate

Upvotes: 1

Views: 240

Answers (2)

Marko Topolnik
Marko Topolnik

Reputation: 200148

Most likely your benchmarking code is not up to standard because benchmarking on the JVM is notoriously tricky due to the distance between Java code you write and the code actually executed by the JVM. If you want really solid results, you should use Google Caliper or Oracle jmh to leverage many years of professional benchmarking. Lacking that, follow at least these guidelines:

  1. create two arrays: one master array, which holds the random data, and the other which will be passed to the sorting methods. Copy the master into the working array each time;
  2. run each kind of sort repeatedly and display the timing for each pass;
  3. observe the times reported. You should witness a drop in the sort time between the first and second run, possibly even further runs. You must run as many times until you see the times have stabilized;

  4. MergeSort, unlike QuickSort, uses dynamic memory allocation. Therefore it will cause the Garbage Collector to steal a portion of the overall time. Control for this with explicit garbage collection, which is once again difficult to achieve. My recommendation for a simple approach that I found workable:

    for (int i = 0; i < 3; i++) { System.gc(); Thread.sleep(500); }

Further than this there are GC tuning paramters, heap sizing, etc. in order to minimize GC while MergeSort is running. On the other hand, GC during MergeSort is a fact of life and it will influence your real-life performance.

Finally, general practice would suggest that QuickSort should be the first choice as long as you don't mind the fact that it is unstable. This property makes it useless when sorting objects on several criteria (first by X, then by Y).

Upvotes: 0

Mario Rossi
Mario Rossi

Reputation: 7799

Another alternative is that you are using the output of one as the input of the next. QuickSort is more sensitive to input "sortedness" (in a positive way) than MergeSort.

Upvotes: 1

Related Questions