Mergesort执行速度很慢

Question

Iam在C++中执行关于不同排序算法的报告。让我感到困惑的是，我的mergesort似乎比两种语言的heapsort都慢。我所看到的是heapsort应该会变慢。

我的mergesort以19.8毫秒的速度排序一个大小为100 000的未排序数组，同时heapsort将它排序为9.7 ms。在C++我的归并函数的代码如下：

void merge(int* array, int low, int mid, int high) 
{ 
int i, j, k; 
int lowLength = mid - low + 1; 
int highLength = high - mid; 


int* lowArray = new int[lowLength]; 
int* highArray = new int[highLength]; 

for (i = 0; i < lowLength; i++) 
    lowArray[i] = array[low + i]; 
for (j = 0; j < highLength; j++) 
    highArray[j] = array[mid + 1 + j]; 

i = 0; 
j = 0; 
k = low; 
while (i < lowLength && j < highLength) 
{ 
    if (lowArray[i] <= highArray[j]) 
    { 
     array[k] = lowArray[i]; 
     i++; 
    } 
    else 
    { 
     array[k] = highArray[j]; 
     j++; 
    } 
    k++; 
} 

while (i < lowLength) 
{ 
    array[k] = lowArray[i]; 
    i++; 
    k++; 
} 

while (j < highLength) 
{ 
    array[k] = highArray[j]; 
    j++; 
    k++; 
} 
} 

void mergeSort(int* array, int low, int high) 
{ 
if (low < high) 
{ 
    int mid = low + (high - low)/2; 

    mergeSort(array, low, mid); 
    mergeSort(array, mid + 1, high); 

    merge(array, low, mid, high); 
} 
} 

Answer 1

示例归并排序是做在合并数据的分配和复制（），并且都能够与更有效的合并排序来消除。临时数组的单个分配可以在辅助函数/入口函数中完成，并且通过使用两个相互递归的函数（如下面的例子）或者使用布尔值来改变合并方向（取决于递归的级别）参数。

下面是一个C++自顶向下合并排序的例子，它被合理地优化了。自底向上合并排序的速度会稍微快一点，而在具有16个寄存器的系统上，4路底部合并的排序速度仍然快一些，快于快速排序。

// prototypes 
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee); 
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee); 
void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee); 

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

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1)     // if size == 1 return 
     return; 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoB(a, b, ll, rr); 
    TopDownSplitMergeAtoB(a, b, rr, ee); 
    TopDownMerge(b, a, ll, rr, ee);  // merge b to a 
} 

void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1){     // if size == 1 copy a to b 
     b[ll] = a[ll]; 
     return; 
    } 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoA(a, b, ll, rr); 
    TopDownSplitMergeAtoA(a, b, rr, ee); 
    TopDownMerge(a, b, ll, rr, ee);  // merge a to b 
} 

void TopDownMerge(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 
     } 
    } 
}