Combining Merge Sort with Insertion Sort

Question

Could someone please advise why this code is not working correctly when threshold is set to <=3? last few digits of array does not get sorted. For example:

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 2 1 }

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 <= 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<=q<=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<q && j<r){
        if(f[i]<=f[j]){
            temp[t] =f[i]; 
            i++;t++;
        }
        else{
            temp[t] = f[j];
            j++;
            t++;
        }

        //tag on remaining sequence
        while(i<q){
            temp[t] = f[i];
            i++;
            t++;

        }
        while(j<r){
            temp[t]=f[j];
            j++;
            t++;
        }
        //copy temp back to f
        i=p;t=0;
        while(t<temp.length){
            f[i]=temp[t];
            i++;
            t++;
        }
        }
}

public static void insertion_srt(int array[], int n, int b){
      for (int i = 1; i < n; i++){
      int j = i;
      int B = array[i];
      while ((j > 0) && (array[j-1] > B)){
      array[j] = array[j-1];
      j--;
      }
      array[j] = B;
     }
    }
}

P.S. code was borrowed from other post Combining MergeSort with Insertion sort to make it more efficient

Answer 1

In insertion_srt() shouldn't the for loop be

    for (int i = n+1; i < b; i++){

and the while loop:

        while ((j > n) && (array[j-1] > B)){

merge() also needs a fix, the trailing brace for the first while loop needs to be moved up before the code to tag on remaining sequences:

    while(i<q && j<r){
        if(f[i]<=f[j]){
            temp[t] =f[i]; 
            i++;
            t++;
        }else{
            temp[t] = f[j];
            j++;
            t++;
        }
    }
    while(i<q){
        temp[t] = f[i];
        i++;
        t++;
    }
    while(j<r){
        temp[t]=f[j];
        j++;
        t++;
    }