StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMergesort running faster on larger inputs
text
Body
copied!<p>I'm working on an empirical analysis of merge sort (sorting strings) for school, and I've run into a strange phenomenon that I can't explain or find an explanation of. When I run my code, I capture the running time using the built in system.nanotime() method, and for some reason at a certain input size, it actually takes <em>less</em> time to execute the sort routine than with a smaller input size. </p> <p>My algorithm is just a basic merge sort, and my test code is simple too:</p> <pre><code>//Get current system time long start = System.nanoTime(); //Perform mergesort procedure a = q.sort(a); //Calculate total elapsed sort time long time = System.nanoTime()-start; </code></pre> <p>The output I got for elapsed time when sorting 900 strings was: 3928492ns For 1300 strings it was: 3541923ns</p> <p>With both of those being the average of about 20 trials, so it's pretty consistent. After 1300 strings, the execution time continues to grow as expected. I'm thinking there might be some peak input size where this phenomenon is most noticeable.</p> <p>So my Question: What might be causing this sudden increase in speed of the program? I was thinking there might be some sort of optimization going on with arrays holding larger amounts of data, although 1300 items in an array is hardly large.</p> <p>Some info:</p> <ul> <li>Compiler: Java version 1.7.0_07</li> <li>Algorithm: Basic recursive merge sort (using arrays)</li> <li>Input type: Strings 6-10 characters long, shuffled (random order)</li> </ul> <p>Am I missing anything?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload