title: MergeSort and insertionSort combination Algorithm running slower together than separately but should run faster
body: <p>I have a mergesort which needs to switch into insertionSort at a specific number, which is my threshold. But my threshold can only be 1, 2 or 3 because in any other cases my mergesort becomes very slow. I cant seem to get the Code to work together.</p>
  
  <p>Here is my code:</p>
  
  <pre><code>public class InsertionSort {
  
      // I haven't found the right Threshold yet, but it should work with any number between 1-100.
  
  public final static int M = 16;
  
      private void Merge(int arr[], int left, int mid, int right) {
          int size1 = mid - left + 1;
          int size2 = right - mid;
  
          int LeftArray[] = new int[size1];
          int RightArray[] = new int[size2];
  
          for (int i = 0; i &lt; size1; ++i) {
              LeftArray[i] = arr[left + i];
  
          }
          for (int j = 0; j &lt; size2; ++j) {
              RightArray[j] = arr[mid + 1 + j];
  
          }
  
          int i = 0;
          int j = 0;
          int k = left;
  
          while (i &lt; size1 &amp;&amp; j &lt; size2) { 
              if (LeftArray[i] &lt;= RightArray[j]) {
                  arr[k] = LeftArray[i];
                  i++;
              } else {
                  arr[k] = RightArray[j];
                  j++;
              }
              k++;
          }
  
  
          while (i &lt; size1) {
              arr[k] = LeftArray[i];
              i++;
              k++;
          }
  
          while (j &lt; size2) {
              arr[k] = RightArray[j];
              j++;
              k++;
          }
  
      }
  
      public void MergeSort(int arr[], int left, int right, int M) {
  
          if ( left &lt; right ) {
  
              int mid = (left + right) / 2;
              MergeSort(arr, left, mid, M);
              MergeSort(arr, (mid+1), right, M);
              Merge(arr, left, mid, right);
      } else if ((right - left + 1) &lt;= M)  {
          insertion_sort(arr, left, right);
      }}
  
  
      static void printArray(int arr[]) {
          int n = arr.length;
          for (int i = 0; i &lt; n; ++i)
              System.out.print(arr[i] + " ");
          System.out.println();
      }
  
      static int[] readIntfile(String filename) throws Exception {
          // Read file into a byte array, and then combine every group of four bytes to an
          // int. (Not
          // the standard way, but it works!)
          byte[] bytes = Files.readAllBytes(Paths.get(filename));
          int[] ints = new int[bytes.length / 4];
          for (int i = 0; i &lt; ints.length; i++) {
              for (int j = 0; j &lt; 4; j++) {
                  ints[i] += (bytes[i * 4 + j] &amp; 255) &lt;&lt; (3 - j) * 8;
              }
          }
          return ints;
  
      }
  
      public static void insertion_sort(int a[], int left, int right) {
          int j;
          for (int i = left; i &lt;= right; i++) {
              int tmp = a[i];
              for (j = i; j &gt; 0 &amp;&amp; tmp &lt; a[j - 1]; j--) {
                  a[j] = a[j - 1];
              }
              a[j] = tmp;
          }
      }
  
  
      public static void main(String args[]) throws Exception {
         // I have texfile named this with 1000000 numbers
           int arr[] = readIntfile("smallints");
  
           // you can also try with this array for example
      // int arr[] = {3, 6, 4, 8, 500, 1, 5, 10, 7, 9, 0, 2, 100, 300, 1000, 20, 13, 17, 55, 93};
          InsertionSort insert = new InsertionSort();
          long before = System.currentTimeMillis();
          insert.MergeSort(arr, 0, arr.length-1, M);
          long after = System.currentTimeMillis();
          printArray(arr);
          System.out.println("\n" + "Done " + ((after - before) / 1000.0 + " sek"));
      }
  }
  </code></pre>