爲什麼插入排序比合並排序更快？

Question

我在jsperf.com上測試了3種排序方法：Bubble，Insertion和Merge。 Link

在測試之前，我使用從0到1Mln的隨機數創建未排序數組。 每次測試顯示Insertion排序比合並排序快。 什麼原因這樣的結果，如果歸併排序時間爲O（n的log（n）），而插入和氣泡各種具有爲O（n^2） test result here

Answer 1

沒有更多的測試，試探性的答案：

你插入排序相當優化 - 你只是開關元件。您的合併排序使用[]實例化新陣列，並使用slice和concat創建新陣列，這是一個很大的內存管理開銷，更不用說concat和slice（儘管在本機代碼中）存在隱式循環。合併排序在原地完成時效率很高;隨着所有複製的進行，這應該會讓你減慢很多。

Answer 2

正如Amadan所評論的那樣，合併排序最好與要排序的數組進行一次性分配。自頂向下合併排序使用遞歸生成合並使用的索引，而自下而上跳過遞歸併使用迭代生成索引。大部分時間將用於子陣列的實際合併，因此自頂向下在超大陣列（100萬或更多）上的額外開銷僅爲5％左右。

示例C++代碼，用於稍微優化自底向上合併排序。

void MergeSort(int a[], size_t n)   // entry function 
{ 
    if(n < 2)        // if size < 2 return 
     return; 
    int *b = new int[n]; 
    BottomUpMergeSort(a, b, n); 
    delete[] b; 
} 

size_t GetPassCount(size_t n)    // return # passes 
{ 
    size_t i = 0; 
    for(size_t s = 1; s < n; s <<= 1) 
     i += 1; 
    return(i); 
} 

void BottomUpMergeSort(int a[], int b[], size_t n) 
{ 
size_t s = 1;        // run size 
    if(GetPassCount(n) & 1){    // if odd number of passes 
     for(s = 1; s < n; s += 2)   // swap in place for 1st pass 
      if(a[s] < a[s-1]) 
       std::swap(a[s], a[s-1]); 
     s = 2; 
    } 
    while(s < n){       // while not done 
     size_t ee = 0;      // reset end index 
     while(ee < n){      // merge pairs of runs 
      size_t ll = ee;     // ll = start of left run 
      size_t rr = ll+s;    // rr = start of right run 
      if(rr >= n){     // if only left run 
       rr = n; 
       BottomUpCopy(a, b, ll, rr); // copy left run 
       break;      // end of pass 
      } 
      ee = rr+s;      // ee = end of right run 
      if(ee > n) 
       ee = n; 
      // merge a pair of runs 
      BottomUpMerge(a, b, ll, rr, ee); 
     } 
     std::swap(a, b);     // swap a and b 
     s <<= 1;       // double the run size 
    } 
} 

void BottomUpCopy(int a[], int b[], size_t ll, size_t rr) 
{ 
    while(ll < rr){       // copy left run 
     b[ll] = a[ll]; 
     ll++; 
    } 
} 

void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee) 
{ 
    size_t o = ll;       // b[]  index 
    size_t l = ll;       // a[] left index 
    size_t r = rr;       // a[] right index 
    while(1){        // merge data 
     if(a[l] <= a[r]){     // if a[l] <= a[r] 
      b[o++] = a[l++];    // copy a[l] 
      if(l < rr)      // if not end of left run 
       continue;     //  continue (back to while) 
      while(r < ee)     // else copy rest of right run 
       b[o++] = a[r++]; 
      break;       //  and return 
     } else {       // else a[l] > a[r] 
      b[o++] = a[r++];    // copy a[r] 
      if(r < ee)      // if not end of right run 
       continue;     //  continue (back to while) 
      while(l < rr)     // else copy rest of left run 
       b[o++] = a[l++]; 
      break;       //  and return 
     } 
    } 
}