title: Combining Merge Sort with Insertion Sort
body: <p>Could someone please advise why this code is not working correctly when threshold is set to &lt;=3? last few digits of array does not get sorted. For example:</p>
  
  <p>input: {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; output: {3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <strong>2 1</strong> }</p>
  
  <pre><code>public class mergesorttest{
      public static void main(String[]args){
          int d[]= {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
          mergeSort(d,0,d.length);
          for(int x:d) System.out.print(x+" "); 
          System.out.println(); 
      }
  
      static final int THRESHOLD = 3;
      static void mergeSort(int f[],int lb, int ub){
          if (ub - lb &lt;= THRESHOLD)
              insertion_srt(f, lb, ub);
          else
          {
              int mid = (lb+ub)/2;
              mergeSort(f,lb,mid);
              mergeSort(f,mid,ub);
              merge(f,lb,mid,ub);
          }
      }
  
  static void merge (int f[],int p, int q, int r){
      //p&lt;=q&lt;=r
      int i =p; int j = q; 
      //use temp array to store merged sub-sequence
      int temp[] = new int[r-p]; int t = 0; 
      while(i&lt;q &amp;&amp; j&lt;r){
          if(f[i]&lt;=f[j]){
              temp[t] =f[i]; 
              i++;t++;
          }
          else{
              temp[t] = f[j];
              j++;
              t++;
          }
  
          //tag on remaining sequence
          while(i&lt;q){
              temp[t] = f[i];
              i++;
              t++;
  
          }
          while(j&lt;r){
              temp[t]=f[j];
              j++;
              t++;
          }
          //copy temp back to f
          i=p;t=0;
          while(t&lt;temp.length){
              f[i]=temp[t];
              i++;
              t++;
          }
          }
  }
  
  public static void insertion_srt(int array[], int n, int b){
        for (int i = 1; i &lt; n; i++){
        int j = i;
        int B = array[i];
        while ((j &gt; 0) &amp;&amp; (array[j-1] &gt; B)){
        array[j] = array[j-1];
        j--;
        }
        array[j] = B;
       }
      }
  }
  </code></pre>
  
  <p>P.S. code was borrowed from other post 
  <a href="https://stackoverflow.com/questions/15057287/combining-mergesort-with-insertion-sort-to-make-it-more-efficient/">Combining MergeSort with Insertion sort to make it more efficient</a></p>