Mergesort实施很慢

Question

我正在做一个关于C ++中不同排序算法的报告。令我感到困惑的是，我的mergesort在两种语言中似乎都比heapsort慢。我所看到的是heapsort应该更慢。

我的mergesort以19.8毫秒的速度对大小为100000的未排序数组进行排序，同时heapsort将其排序为9.7毫秒。我在c ++中使用mergesort函数的代码如下：

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

示例合并排序是在merge（）中进行数据的分配和复制，并且可以通过更有效的合并排序来消除这两者。临时数组的单个分配可以在辅助/入口函数中完成，并且通过使用两个相互递归的函数（如下面的示例）或使用布尔值，通过根据递归的级别更改合并的方向来避免复制参数。

以下是合理优化的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
        }
    }
}