title: Algorithms: Hybrid MergeSort and InsertionSort Execution Time
body: <p>Good day SO community,</p>
  
  <p>I am a CS student currently performing an experiment combining MergeSort and InsertionSort. It is understood that for a certain threshold, S, InsertionSort will have a quicker execution time than MergeSort. Hence, by merging both sorting algorithms, the total runtime will be optimized.</p>
  
  <p>However, after running the experiment many times, using a sample size of 1000, and varying sizes of S, the results of the experiment does not give a definitive answer each time. Here is a picture of the better results obtained (Note that half of the time the result is not as definitive):</p>
  
  <p><a href="https://i.stack.imgur.com/O0wen.png" rel="noreferrer"><img src="https://i.stack.imgur.com/O0wen.png" alt="Execution Time for varying sizes of S, with sample size of 1000. Original Mergesort vs Hybrid Mergesort"></a></p>
  
  <p>Now, trying the same algorithm code with a sample size of 3500:</p>
  
  <p><a href="https://i.stack.imgur.com/40J9R.png" rel="noreferrer"><img src="https://i.stack.imgur.com/40J9R.png" alt="enter image description here"></a></p>
  
  <p>Finally, trying the same algorithm code with a sample size of 500,000 (Note that the y-axis is in milliseconds:</p>
  
  <p><a href="https://i.stack.imgur.com/nTi9H.png" rel="noreferrer"><img src="https://i.stack.imgur.com/nTi9H.png" alt="enter image description here"></a></p>
  
  <p>Although logically, the Hybrid MergeSort will be faster when S&lt;=10, as InsertionSort does not have recursive overhead time. However, the results of my mini experiment says otherwise.</p>
  
  <p>Currently, these are the Time Complexities taught to me:</p>
  
  <p>MergeSort: O(n log n)</p>
  
  <p>InsertionSort:</p>
  
  <ul>
  <li>Best Case: θ(n)</li>
  <li>Worst Case: θ(n^2)</li>
  </ul>
  
  <p>Finally, I have found an online source: <a href="https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort">https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort</a> that states that:</p>
  
  <p>Hybrid MergeInsertionSort:</p>
  
  <ul>
  <li>Best Case: θ(n + n log (n/x))</li>
  <li>Worst Case: θ(nx + n log (n/x)) </li>
  </ul>
  
  <p>I would like to ask if there are results in the CS community that shows <strong>definitive proof that a Hybrid MergeSort algorithm will work better than a normal MergeSort algorithm below a certain threshold, S, and if so, why</strong>?</p>
  
  <p>Thank you so much SO community, it might be a trivial question, but it really will clarify many questions that I currently have regarding Time Complexities and stuff :)</p>
  
  <p>Note: I am using Java for the coding of the algorithm, and runtime could be affected by the way java stores data in memory..</p>
  
  <p>Code in Java:</p>
  
  <pre><code> public static int mergeSort2(int n, int m, int s, int[] arr){
          int mid = (n+m)/2, right=0, left=0;
          if(m-n&lt;=s)
              return insertSort(arr,n,m);
          else
          {
              right = mergeSort2(n, mid,s, arr);
              left = mergeSort2(mid+1,m,s, arr);
              return right+left+merge(n,m,s,arr);
          }      
      }
  
      public static int insertSort(int[] arr, int n, int m){
          int temp, comp=0;
          for(int i=n+1; i&lt;= m; i++){
              for(int j=i; j&gt;n; j--){ 
                  comp++;
                  comparison2++;
                  if(arr[j]&lt;arr[j-1]){
                      temp = arr[j];
                      arr[j] = arr[j-1];
                      arr[j-1] = temp;
                  }
                  else
                      break;
              }
          }
          return comp;
      }
  
      public static void shiftArr(int start, int m, int[] arr){
          for(int i=m; i&gt;start; i--)
              arr[i] = arr[i-1];     
      }
  
  public static int merge(int n, int m, int s, int[] arr){
          int comp=0;
          if(m-n&lt;=s)
              return 0;
          int mid = (n+m)/2;
          int temp, i=n,  j=mid+1;
          while(i&lt;=mid &amp;&amp; j&lt;=m)
          {
              comp++;
              comparison2++;
  
  
              if(arr[i] &gt;= arr[j])
              {
                  if(i==mid++&amp;&amp;j==m &amp;&amp; (arr[i]==arr[j]))
                      break;
                  temp = arr[j];
                  shiftArr(i,j++,arr);
                  arr[i] = temp;
                  if(arr[i+1]==arr[i]){
                     i++;
                  }
              }
              i++;
  
  
          }
          return comp;
      }
  </code></pre>