MergeSort與插入排序組合，使其更有效

Question

所以我有一個MergeSort算法，我想結合MergeSort和插入排序來減少合併的開銷，問題是如何？我想使用插入排序對段進行排序，然後合併。

public class mergesorttest{ 
    public static void main(String[]args){ 
     int d[]= {10,2,3,4,5,6,5,4,3,5,6,7,1}; 
     mergeSort(d,0,d.length); 
     for(int x:d) System.out.print(x+" "); 
     System.out.println(); 
    } 

static void mergeSort(int f[],int lb, int ub){ 
    //termination reached when a segment of size 1 reached -lb+1=ub 
    if(lb+1<ub){ 
     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; 
    } 
    } 

Answer 1

的自動合併負責排序的元素。然而，當列表變得低於某一閾值可以使用排序插入排序：

static final int THRESHOLD = 10; 
static void mergeSort(int f[],int lb, int ub){ 
    if (ub - lb <= THRESHOLD) 
     insertionSort(f, lb, ub); 
    else 
    { 
     int mid = (lb+ub)/2; 
     mergeSort(f,lb,mid); 
     mergeSort(f,mid,ub); 
     merge(f,lb,mid,ub); 
    } 
} 

做得比這個其他（除與閾值一點點打轉轉）很少會增加通過合併排序所花費的時間。

雖然合併排序是O（n log n），插入排序是O（n ），但插入排序具有更好的常量，因此在非常小的數組上更快。 This,this,this和this是我發現的幾個相關問題。

Answer 2

public static final int K = 5; 

public static void insertionSort(int A[], int p, int q) { 
    for (int i = p; i < q; i++) { 
     int tempVal = A[i + 1]; 
     int j = i + 1; 
     while (j > p && A[j - 1] > tempVal) { 
      A[j] = A[j - 1]; 
      j--; 
     } 
     A[j] = tempVal; 
    } 
    int[] temp = Arrays.copyOfRange(A, p, q +1); 
    Arrays.stream(temp).forEach(i -> System.out.print(i + " ")); 
    System.out.println(); 
} 

public static void merge(int A[], int p, int q, int r) { 
    int n1 = q - p + 1; 
    int n2 = r - q; 
    int[] LA = Arrays.copyOfRange(A, p, q +1); 
    int[] RA = Arrays.copyOfRange(A, q+1, r +1); 
    int RIDX = 0; 
    int LIDX = 0; 
    for (int i = p; i < r - p + 1; i++) { 
     if (RIDX == n2) { 
      A[i] = LA[LIDX]; 
      LIDX++; 
     } else if (LIDX == n1) { 
      A[i] = RA[RIDX]; 
      RIDX++; 
     } else if (RA[RIDX] > LA[LIDX]) { 
      A[i] = LA[LIDX]; 
      LIDX++; 
     } else { 
      A[i] = RA[RIDX]; 
      RIDX++; 
     } 
    } 
} 

public static void sort(int A[], int p, int r) { 
    if (r - p > K) { 
     int q = (p + r)/2; 
     sort(A, p, q); 
     sort(A, q + 1, r); 
     merge(A, p, q, r); 
    } else { 
     insertionSort(A, p, r); 
    } 
} 

public static void main(String string[]) { 
    int[] A = { 2, 5, 1, 6, 7, 3, 8, 4, 9 }; 
    sort(A, 0, A.length - 1); 
    Arrays.stream(A).forEach(i -> System.out.print(i + " ")); 
}