算法：混合歸併和插入排序執行時間

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