算法：混合归并和插入排序执行时间

Question

日安SO社区，

我目前进行的实验相结合归并和插入排序一个CS的学生。据了解，对于某个阈值，S，InsertionSort的执行时间比MergeSort快。因此，通过合并两种排序算法，总运行时间将得到优化。

但是，在运行实验多次后，使用1000的样本大小和不同大小的S，实验结果并没有给出明确的答案。下面是获得更好的效果的照片（注意时间一半的结果不明确）：

现在，3500样本大小尝试相同的算法代码：

最后，试图用的500000样本大小相同的算法代码（请注意，在y轴的单位是毫秒：

虽然在逻辑上，当S < = 10时，Hybrid MergeSort会更快，因为InsertionSort没有递归开销时间。但是，我的小型实验的结果却另有说明。

目前，这些都是时间复杂度教给我：

归并：为O（n log n）的

插入排序：

• 最佳案例：θ（N）
• 最差案例：θ（n^2）

最后，我找到了一个在线来源：https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort，指出：

混合MergeInsertionSort：

• 最佳情况：θ（N + N日志（N/X））
• 最坏情况：θ（NX + N日志（N/X） ）

我想问一下，如果有结果的CS界，显示明确的证据证明混合归并算法会更好地工作比低于某一阈值，S正常归并算法，如果是这样，为什么？

太谢谢你了SO社区，这可能是一个微不足道的问题，但它真的会澄清，我现在有关于时间复杂度和东西:)许多问题

注：我使用Java进行编码算法和运行时可能会受到java将数据存储在内存中的方式的影响。

代码Java中：

public static int mergeSort2(int n, int m, int s, int[] arr){ 
     int mid = (n+m)/2, right=0, left=0; 
     if(m-n<=s) 
      return insertSort(arr,n,m); 
     else 
     { 
      right = mergeSort2(n, mid,s, arr); 
      left = mergeSort2(mid+1,m,s, arr); 
      return right+left+merge(n,m,s,arr); 
     }  
    } 

    public static int insertSort(int[] arr, int n, int m){ 
     int temp, comp=0; 
     for(int i=n+1; i<= m; i++){ 
      for(int j=i; j>n; j--){ 
       comp++; 
       comparison2++; 
       if(arr[j]<arr[j-1]){ 
        temp = arr[j]; 
        arr[j] = arr[j-1]; 
        arr[j-1] = temp; 
       } 
       else 
        break; 
      } 
     } 
     return comp; 
    } 

    public static void shiftArr(int start, int m, int[] arr){ 
     for(int i=m; i>start; i--) 
      arr[i] = arr[i-1];  
    } 

public static int merge(int n, int m, int s, int[] arr){ 
     int comp=0; 
     if(m-n<=s) 
      return 0; 
     int mid = (n+m)/2; 
     int temp, i=n, j=mid+1; 
     while(i<=mid && j<=m) 
     { 
      comp++; 
      comparison2++; 


      if(arr[i] >= arr[j]) 
      { 
       if(i==mid++&&j==m && (arr[i]==arr[j])) 
        break; 
       temp = arr[j]; 
       shiftArr(i,j++,arr); 
       arr[i] = temp; 
       if(arr[i+1]==arr[i]){ 
        i++; 
       } 
      } 
      i++; 


     } 
     return comp; 
    } 

Answer 1

示例代码是不是一个传统的合并排序。合并函数正在移动一个数组，而不是在原始数组和临时工作数组之间合并运行并返回。

我测试了自顶向下和自下而上的合并排序，两者都需要大约42毫秒== 0.042秒来排序500,000个32位整数，而图中明显的结果是大约42秒而不是42毫秒慢1000倍。我还用10,000,000个整数进行了测试，需要1秒多的时间进行排序。在过去，使用C++，我将自底向上合并排序与混合自底向上合并/插入排序进行了比较，对于1600万（2^24 == 16,777,216）32位整数，混合排序大约为8与S == 16更快。S == 64比S == 16稍慢。Visual Studio std :: stable_sort是自底向上合并排序的一种变体（temp数组是原始数组大小的1/2）和插入排序，并使用小号== 32.

对于小阵列，插入排序是快于归并排序，高速缓存局部性和排序小阵列插入排序需要较少指令的组合。对于伪随机数据和S == 16至64，插入排序大约是合并排序的两倍。

的相对增益减小作为数组的大小增加而增加。考虑到对自下而上合并排序的影响，对于S == 16，仅优化了4个合并流程。在我的测试用例中，有2^24 == 16,777,216个元素，这是4/24 = 1/6〜=传递数量的16.7％，导致大约8％的改进（所以插入排序大约是合并速度的两倍为那4次传球排序）。合并时间仅为1.52秒，混合排序时间约为1.40秒，仅需1.52秒即可获得0.12秒的增益。对于自顶向下的合并排序，S == 16，递归的4个最深层次将被优化。

更新 - 代替一个混合实施例的Java代码合并带O排序/插入排序（N日志（n））的时间复杂度。 （注意 - 由于递归，辅助存储仍然在堆栈中消耗。）就地部分在合并步骤中通过交换合并区域中的数据与合并区域中的数据来完成。这不是一个稳定的排序（由于在合并步骤中进行交换，所以不会保留相同元素的顺序）。对500,000个整数进行排序大约需要1/8秒，所以我将其增加到了1600万（2^24 == 16777216）个整数，这需要4秒多一点的时间。如果没有插入排序，排序大约需要4.524秒，而使用S == 64插入排序的排序大约需要4.150秒，大约增加8.8％。 C中的代码基本相同，但改善程度较低：从2.88秒到2.75秒，大约增加4.5％。

package msortih; 
import java.util.Random; 

public class msortih { 

    static final int S = 64; // use insertion sort if size <= S 

    static void swap(int[] a, int i, int j) { 
     int tmp = a[i]; a[i] = a[j]; a[j] = tmp; 
    } 

    // a[w:] = merged a[i:m]+a[j:n] 
    // a[i:] = reordered a[w:] 
    static void wmerge(int[] a, int i, int m, int j, int n, int w) { 
     while (i < m && j < n) 
      swap(a, w++, a[i] < a[j] ? i++ : j++); 
     while (i < m) 
      swap(a, w++, i++); 
     while (j < n) 
      swap(a, w++, j++); 
    } 

    // a[w:] = sorted a[b:e] 
    // a[b:e] = reordered a[w:] 
    static void wsort(int[] a, int b, int e, int w) { 
     int m; 
     if (e - b > 1) { 
      m = b + (e - b)/2; 
      imsort(a, b, m); 
      imsort(a, m, e); 
      wmerge(a, b, m, m, e, w); 
     } 
     else 
      while (b < e) 
       swap(a, b++, w++); 
    } 

    // inplace merge sort a[b:e] 
    static void imsort(int[] a, int b, int e) { 
     int m, n, w, x; 
     int t; 
     // if <= S elements, use insertion sort 
     if (e - b <= S){ 
      for(n = b+1; n < e; n++){ 
       t = a[n]; 
       m = n-1; 
       while(m >= b && a[m] > t){ 
        a[m+1] = a[m]; 
        m--;} 
       a[m+1] = t;} 
      return; 
     } 
     if (e - b > 1) { 
      // split a[b:e] 
      m = b + (e - b)/2; 
      w = b + e - m; 
      // wsort -> a[w:e] = sorted a[b:m] 
      //   a[b:m] = reordered a[w:e] 
      wsort(a, b, m, w); 
      while (w - b > 2) { 
       // split a[b:w], w = new mid point 
       n = w; 
       w = b + (n - b + 1)/2; 
       x = b + n - w; 
       // wsort -> a[b:x] = sorted a[w:n] 
       //   a[w:n] = reordered a[b:x] 
       wsort(a, w, n, b); 
       // wmerge -> a[w:e] = merged a[b:x]+a[n:e] 
       //   a[b:x] = reordered a[w:n] 
       wmerge(a, b, x, n, e, w); 
      } 
      // insert a[b:w] into a[b:e] using left shift 
      for (n = w; n > b; --n) { 
       t = a[n-1]; 
       for (m = n; m < e && a[m] < t; ++m) 
        a[m-1] = a[m]; 
       a[m-1] = t; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     int[] a = new int[16*1024*1024]; 
     Random r = new Random(0); 
     for(int i = 0; i < a.length; i++) 
      a[i] = r.nextInt(); 
     long bgn, end; 
     bgn = System.currentTimeMillis(); 
     imsort(a, 0, a.length); 
     end = System.currentTimeMillis(); 
     for(int i = 1; i < a.length; i++){ 
      if(a[i-1] > a[i]){ 
       System.out.println("failed"); 
       break; 
      } 
     } 
     System.out.println("milliseconds " + (end-bgn)); 
    } 
}