Объединение Сортировка с сортировкой Сортировка

Question

Может кто-нибудь, пожалуйста, сообщите, почему этот код работает неправильно, когда порог установлен на < = 3? последние несколько цифр массива не сортируются. Например:

ввод: {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1} ; Выход: {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. код был заимствован из другого поста Combining MergeSort with Insertion sort to make it more efficient

Answer 1

В insertion_srt() не должно для цикла быть

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

и петля в то время:

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

слияния() также необходимо исправить, конечная скобка для первого цикла while должна быть перемещена вверх до того, как код будет помечен на оставшихся последовательностях:

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++; 
    }