将MergeSort与插入排序相结合，使其更有效

所以我有一个MergeSort算法，我想将MergeSort与Insertion排序相结合，以减少合并的开销，问题是如何？ 我想使用插入排序对段进行排序，然后合并。

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[rp]; 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  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 ² ），但插入排序具有更好的常量，因此在非常小的数组上更快。 这个 ， 这个和我发现的一些相关问题。

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