title: Understanding why/how Java's native sorting of an int array is optimized on successive sorts...so I can stop it
body: <p><strong>My program in a nutshell:</strong></p>
  <p>I have a program that successively runs several sort algorithms against an array of ints, timing each. The GUI allows the user to select array size and a variety of random number ranges with which to fill the array to be sorted. Each click of the &quot;Sort&quot; button grabs the user's array values, constructs a new array, then creates for each sort algorithm a clone of the array, using <code>.clone()</code>.</p>
  <p><strong>The problem:</strong></p>
  <p>when &quot;sort&quot; button is clicked a second time the sorts improve themselves.</p>
  <p><strong>Somewhere there's optimization happening that I don't understand.</strong></p>
  <p>The reason this is an issue: if the user doesn't change their array settings and runs the sort methods again, it is true that a new array is constructed with new random numbers but the random number ranges remain the same so the run time, over a list of 125k, should remain about the same....not improve 300%.</p>
  <p>So here is a demo program of what I am facing. It uses only one sort, Java's native sort to demonstrate the issue. It also uses hard coded values for constructing the random int array to be sorted - but does so with each &quot;enter&quot; press. I think this simulation accurately reflects my program because the same &quot;error&quot; is happening here, too.</p>
  <h2>Why is the sort faster the second time?</h2>
  <p>...the array is rebuilt with new values for each run, so how can it get faster?</p>
  <pre><code>package sortTooFast;
  
  import java.util.Arrays;
  import java.util.Scanner;
  
  public class SortTooFast {
      public static final int ARRAY_SIZE = 500000;
      public static final int MIN_RANGE = 0;
      public static final int MAX_RANGE = 100;
      public static final int INCLUSIVE = 1;
      
      int[] sortingArray;
  
      public static void main(String[] args) {
          SortTooFast test = new SortTooFast();
          test.run();
      }
      
      // Run program.
      public void run(){
          while(true){    
              
              // Assign int[] filled with random numbers.
              sortingArray = getArray();                  
  
              // Inform user.
              System.out.println(&quot;\nPress return key to run sort!&quot;);
              
              // Wait for user.
              new Scanner(System.in).nextLine();
              
              System.out.println(&quot;First 15 elements to be sorted:&quot;);
              
              // Print a small section of the array; prove not sorted
              for (int i = 0; i &lt; 15; i++){
                  System.out.printf(&quot;%4d&quot;, sortingArray[i]);
              }
              
              // Perform sort.
              runNativeSort(sortingArray);
          }
      }
  
      // Run native java sort.
      private void runNativeSort(int[] array) {
          // Start timer
          long startTime = System.currentTimeMillis();
          
          // Perform sort.
          Arrays.sort(array);
          
          // End timer
          long finishTime = System.currentTimeMillis();
          
          // Running time.
          long runTime = finishTime - startTime;
          
          // Report run time.
          System.out.println(&quot;\nRun time: &quot; +runTime);        
      }
  
      // Obtain an array filled with random int values.
      private int[] getArray() {
          // Make int array.
          int[] mArray = new int[ARRAY_SIZE];
          
          // Length of array.
          int length = mArray.length;
          
          // Fill array with random numbers.
          for(int counter = 0; counter &lt; length; counter++){
              int random = MIN_RANGE + (int)(Math.random() * ((MAX_RANGE - MIN_RANGE) + INCLUSIVE));
              mArray[counter] = random;
          }
          return mArray;
      }
  }
  </code></pre>