Mergesort的执行速度很慢 [英] Mergesort implementation is slow

问题描述

我正在撰写有关C ++中不同排序算法的报告.使我感到困惑的是，在两种语言中，我的mergesort似乎都比heapsort慢.我所看到的是heapsort应该更慢.

I'am doing a report about different sorting algorithms in C++. What baffles me is that my mergesort seems to be slower than heapsort in both of the languages. What I've seen is that heapsort is supposed to be slower.

我的mergesort以19.8 ms的速度对大小为100000的未排序数组进行排序，而heapsort以9.7 ms的速度对其进行排序.我在C ++中的mergesort函数的代码如下:

My mergesort sorts an unsorted array with size 100000 at a speed of 19.8 ms meanwhile heapsort sorts it at 9.7 ms. The code for my mergesort function in C++ is as follows:

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

推荐答案

示例合并排序是在merge()中进行数据的分配和复制，并且可以通过更有效的合并排序来消除两者.可以在helper/entry函数中完成对temp数组的单个分配，并且可以通过使用两个相互递归的函数(如下面的示例)或使用布尔值来根据递归的级别更改合并的方向来避免复制参数.

The example merge sort is doing allocation and copying of data in merge(), and both can be eliminated with a more efficient merge sort. A single allocation for the temp array can be done in a helper / entry function, and the copy is avoided by changing the direction of merge depending on level of recursion either by using two mutually recursive functions (as in example below) or with a boolean parameter.

这里是经过合理优化的C ++自上而下合并排序的示例.自底向上合并排序会稍快一些，在具有16个寄存器的系统上，四向底合并排序仍然要快一些，大约快于快速排序.

Here is an example of a C++ top down merge sort that is reasonably optimized. A bottom up merge sort would be slightly faster, and on a system with 16 registers, a 4 way bottom merge sort a bit faster still, about as fast or faster than quick sort.

// 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
        }
    }
}

这篇关于Mergesort的执行速度很慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！