将c++中的排序与除法3合并

Question

如何编写合并排序，但将其划分为3

int merge_sort(int input[], int p, int r)
{
    if ( p >= r )
        return 0; 

    int mid = floor((p + r) / 2);
    merge_sort(input, p, mid);
    **merge_sort(input, mid + 1, r);** 
    merge(input, p, r);
}

Answer 1

这可能是一个3路合并。您可能需要考虑使用自下而上合并排序。对于自上而下或自下而上的合并，大多数复杂性都将出现在合并函数中。正如在由zwergmaster链接的答案中所提到的，这是一个运行的3路合并。每次运行都需要一个当前和结束的索引或指针。if / end语句的序列最后执行两次比较，以确定3次运行中哪一次具有最小的元素，然后将该最小的元素移动到目标数组(或向量或.)然后检索运行中的下一个元素。当到达3次运行中的一次结束时，代码切换为双向合并。当到达下一次运行的结束时，代码将复制其余的运行。然后合并下一组3次运行，重复该进程，直到到达数组结束为止，这可能发生在3次运行中的任何一次，因此在数组结束附近的最后一次合并可能是3或2次运行的合并，或者只是1 run的副本。

如果有一个初始函数来分配与要排序的数组大小相同的临时数组，则会更有效，然后让它调用将临时数组作为参数传递的合并排序函数，而不是在合并排序过程中不断分配和释放小型临时数组。

因此，使用自顶向下的合并排序部分代码来帮助解释这一点：

merge_sort(int *a, int n)
{
    int *b = new int[n];
    top_down_merge_sort(a, b, 0, n);
    /* ... */
    delete[] b;
}

top_down_merge_sort(int *a, int *b, int beg, int end)
{
    if(end - beg < 3){
        /* sort in place */
        return;
    }
    int run0 = beg;
    int run1 = beg +   (end-beg)/3;
    int run2 = beg + 2*(end-beg)/3;
    top_down_merge_sort(a, b, run0, run1);
    top_down_merge_sort(a, b, run1, run2);
    top_down_merge_sort(a, b, run2, end);
    merge_runs(a, b, run0, run1, run2, end);
}