title: I'm merge sorting int arrays of length 10,000 to 75,000. I am getting strange sort times. Why might this be?
body: <p>I am doing an assignment for my algorithm class and I have to demonstrate that internal merge sort has a time complexity of <strong>O(n log n)</strong>. To do this I made arrays ranging in length from 10,000 elements long to 75,000 elements long. Then I load the array with random numbers below 10,000, and output the array length to the console with how long it took to sort. </p>
  
  <p>The strange result is that some take ~15 milliseconds give or take and then others take 0 milliseconds, even if the array is tens of thousands of integers longer. Any idea of why this may be? I can upload a screen shot of my output, but someone needs to approve it because I don't have enough "reputation". I have checked the arrays. They do appear to be sorted after calling the <code>mergeSort()</code> method.</p>
  
  <pre><code>public static void main(String[] args){
      int[] dataLength = { 10_000, 15_000, 20_000, 25_000, 30_000,
                           35_000, 40_000, 45_000, 50_000, 55_000,
                           60_000, 65_000, 70_000, 75_000 };
      // internal merge sort
      for (int i = 0; i &lt; dataLength.length; i++) {
          int[] input = new int[dataLength[i]];
          for (int j = 0; j &lt; input.length; j++) {
              input[j] = random.nextInt(10000);
          }
  
          long startTime = System.currentTimeMillis();
          mergeSort(input, 0, input.length);
          long endTime = System.currentTimeMillis();
  
          System.out.println("Length of array is: " + input.length + ". The sorted array: " +
                             Arrays.toString(input));
          System.out.println("Internal sort with " + dataLength[i] + " items took: " +
                             (endTime - startTime) + " milliseconds");
      }
  }
  
  public static void mergeSort(int[] input, int start, int end) {
      if (end - start &lt; 2) {
          return;
      }
  
      int mid = (start + end) / 2;
      mergeSort(input, start, mid);
      mergeSort(input, mid, end);
      merge(input, start, mid, end);
      return;
  }
  
  public static void merge(int[] input, int start, int mid, int end) {
      if (input[mid - 1] &lt;= input[mid]) {
          return;
      }
   //        index of "left" array
      int i = start;
   //        index of "right" array
      int j = mid;
      int tempIndex = 0;
      int[] temp = new int[end - start];
  
      while (i &lt; mid &amp;&amp; j &lt; end) {
          temp[tempIndex++] = input[i] &lt;= input[j] ? input[i++] : input[j++];
      }
   //        optimizes the merge. If there are elements in the left array we just copy them back
   //        into the input array instead of merging them with the temp array first
      System.arraycopy(input, i, input, start + tempIndex, mid - i);
      System.arraycopy(temp, 0, input, start, tempIndex);
      return;
  }
  </code></pre>