c++ - 归并排序实现

Question

我是 C++ 新手，正在尝试开发合并排序代码。我用大小为 5 的样本数组对其进行了测试，但代码给出的答案是不正确的。我不知道出了什么问题。这是我的代码:

#include <iostream>
#include <cstring>
#include <sstream>
#include <fstream>
#include <iomanip>
using namespace std;
void merge(int, int, int, int*);
void merge_sort(int low, int high, int* p){
    int pivot;
    static int i(1);
    if (high>low)
    {
        cout << "calling merge_sort: "<<i<<endl; i++;
        pivot = low + ((high - low)/2);
        cout << pivot << endl;
        merge_sort(low, pivot, p);
        merge_sort(pivot+1, high, p);
        merge(low, pivot, high, p);

    }
}
void merge(int l, int pi, int h,int* arr)
{
            int start = l;
        int mid = pi+1;
        while((start<=pi)&&(mid <=h)){
            if (arr[start] > arr[mid])
            {
                int temp = arr[mid];
                arr[mid] = arr[start];
                arr[start] = temp;
                mid++;
             }
            else
                start++;
    }
}
int main() 
{
    int a[] = {2, 42, 3, 7, 1};
    merge_sort(0, 4, a);
    for (int i = 0; i<=4 ; i++)
        cout << a[i] << endl;
    return (0);

}

输出如下:

calling merge_sort: 1
2
calling merge_sort: 2
1
calling merge_sort: 3
0
calling merge_sort: 4
3
1
3
7
2
42

我在 stackoverflow 上看到了一些合并排序实现的代码，但它们使用了另一个我想避免的临时数组。

在解决此问题时非常感谢任何帮助。

Answer 1

你合并的逻辑是错误的。在合并阶段，您知道您有 2 个已排序数字部分。当您比较和交换 arr[start] 和 arr[mid] 时，如果 arr[start] > arr[中+1]。该示例显示您的代码存在问题，因为 2 将留在错误的位置:

4 6 8 | 1 3 5  ->  1 6 8 | 4 3 5
^       ^          ^         ^

为了保持 2 个部分的排序，您必须在顶部数字集中的正确位置插入 arr[start]，这会使复杂度比 O(n LG n)。这就是使用第二个数组的原因。

有些方法使用比原始数组更小的数组进行合并，这些方法有其开销但不会影响复杂性(或正确性)。如果您想要一个 O(n lg n) 就地排序，那么快速排序或堆排序是可行的方法。