归并排序的实现

我是 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 上看到了一些合并排序实现的代码，但它们使用了另一个临时数组，我想避免这种情况。

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

你的合并逻辑是错误的。在合并阶段，您知道您有 2 部分已排序的数字。当你比较和交换时arr[start] and arr[mid]如果出现以下情况，您将破坏顶部数字集的排序arr[start] > arr[mid+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)就地排序然后快速排序或堆排序是可行的方法。