title: Why is my mergeSort / shellSort slower than insertion sort
body: <p>I have an array of 100000 elements which i have filled with random numbers form 0-999999<br>
  this is my    <strong>Merge sort</strong> <strong>code</strong> :</p>
  
  <pre><code>private static void sortArray(int[] data, int low, int high)
  {
      if ((high - low) &gt;= 1)
      {
          int middle1 = (low + high) / 2;
          int middle2 = middle1 + 1;
          sortArray(data, low, middle1);
          sortArray(data, middle2, high);
          merge (data, low, middle1, middle2, high);
      }
  }
  
  private static void merge(int[] data, int left, int middle1,
                            int middle2, int right)
  {
      int leftIndex = left;
      int rightIndex = middle2;
      int combinedIndex = left;
      int[] combined = new int[data.length];
  
      while (leftIndex &lt;= middle1 &amp;&amp; rightIndex &lt;= right)
      {
          if (data[leftIndex] &lt;= data[rightIndex]){
              combined[combinedIndex++] = data[leftIndex++];
          }
          else{
              combined[combinedIndex++] = data[rightIndex++];
          }
      }
  
      if (leftIndex == middle2){
  
          while (rightIndex &lt;= right)
              combined[combinedIndex++] = data[rightIndex++];
      }
      else {
          while (leftIndex &lt;= middle1)
              combined[combinedIndex++] = data[leftIndex++];
      }
      for (int i = left; i &lt;= right; i++)
          data[i] = combined[i];
  
  }
  </code></pre>
  
  <p>This is my <code>shellSort</code> code:</p>
  
  <pre><code>public static void shellSort(){
  
      int inner , outer , temp;
      int interval = 1;
      while(interval &lt; arraysize/3){
          interval = interval*3+1;
      }
      while(interval &gt; 0){
          for(outer = interval; outer&lt;arraysize; outer++){
              inner = outer;
              temp = array[inner];
              while(inner &gt; interval-1 &amp;&amp; array[inner-interval] &gt;= temp){
                  array[inner] = array[inner-interval];
                  inner = inner - interval;
              }
                  array[inner] = temp;
          }
              interval = (interval-1)/3;
      }       
  }
  </code></pre>
  
  <p>and this is my <strong>insertionSort</strong> :</p>
  
  <pre><code>  public  static void insertionSort(){
  
      for(int i = 1; i &lt; arraysize; i++){
  
          int value = array[i];
          int index = i;
          while(index &gt; 0 &amp;&amp; value &lt; array[index-1]){
              array[index] = array[index-1];
              index--;
          }
          array[index] = value;
      }
  }
  </code></pre>
  
  <p>And this is the time code:</p>
  
  <pre><code>    start = System.nanoTime();
      shellSort();
      end = System.nanoTime();
      System.out.println("shellsort took " + (end-start) + " nanosecs");
  
      start = System.nanoTime();
      sortArray(array , 0 , arraysize-1);
      end = System.nanoTime();
      System.out.println("mergesort took " + (end-start) + " nanosecs");
  
      start = System.nanoTime();
      insertionSort();
      end = System.nanoTime();
      System.out.println("insertionsort took " + (end-start) + " nanosecs");
  </code></pre>
  
  <p><strong>Time :</strong>
  shellsort took 25301559 nanosecs<br>
  mergesort took 41976634024 nanosecs<br>
  insertionsort took 2337867 nanosecs</p>