合并排序实现

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

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

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

为了保持两个部分的排序，你必须在最上面一组数字中的正确位置插入arr[start]，这会使复杂度比O(n lg n)更糟糕。这就是使用第二个数组的原因。

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

Answer 2

下面是一个整数数组合并排序的实现：

void merge_sort (int array[], int size)
{
    int temp[size];
    int mid, i;
    if (size < 2) {
        return;
    } 
    else {
        mid = size / 2;
        merge_sort(array, mid);
        merge_sort(array + mid, size - mid);
        merge (array, mid, array + mid, size - mid, temp);
        for (i = 0; i < size; i++) {
            array[i] = temp[i];
        }
    }
}

int  merge  (int list1[ ] , int size1 , int list2[ ] , int size2 , int list3[ ])
{
    int i1, i2, i3;
    if (size1+size2 > size) {
        return false;
    }
    i1 = 0; i2 = 0; i3 = 0;
    /* while both lists are non-empty */
    while (i1 < size1 && i2 < size2) {
        if (list1[i1] < list2[i2]) {
            list3[i3++] = list1[i1++];
        } 
        else {
            list3[i3++] = list2[i2++];
        }
    }
    while (i1 < size1) {   
        /* copy remainder of list1 */
        list3[i3++] = list1[i1++];
    }
    while (i2 < size2) { 
        /* copy remainder of list2 */
        list3[i3++] = list2[i2++];
    }
    return true;
}

如果您想将其用于其他类型，则可以在c++模板中使用，如下所示：

    template <class T>
T* merge_sort(T arr[], int n)
{
    if(n < 2){return arr;}
    int mid = n/2;
    T *arr1 = merge_sort<T>(arr,mid);
    T *arr2 = merge_sort<T>(arr+mid,n-mid); 
    return merge(arr1, mid, arr2, n-mid);
}

template <class T>
T* merge(T arr1[], int size1, T arr2[], int size2)
{
    int i = 0,j = 0;

    T* out_array = new T[size1+size2];

    while((i < size1) && (j < size2))
    {
        if(arr1[i] >= arr2[j])
        {
            out_array[i+j] = arr2[j];
            ++j;
        }
        else
        {
            out_array[i+j] = arr1[i];
            ++i;
        } 
    }
    while(i < size1)
    {
        //copy the reminder
        out_array[i+j] = arr1[i];
        i++;
    }
    while( j < size2)
    {
        out_array[i+j] = arr2[j];
        j++;
    }
    return out_array;
}

但有以下情况：

 #include <iostream>
using namespace std;

int main() {
    int a[] = {2, 42, 3, 7, 1};
     int *a2 = merge_sort(a,5);
    for (int i = 0; i<= 4 ; ++i)
        cout << a2[i] << endl;
    return (0);
}

输出：

1
2
3
7
42

希望我能帮上点忙。

Answer 3

在我看来，这几行似乎是错误的：

int temp = arr[mid-1]; // It should be [mid] here
arr[mid] = arr[start]; // Or [mid-1] here
arr[start] = temp;

对于交换两个索引，这两个索引必须匹配。