C++ 合并排序实现

Merge sort implementation

提问by akash_c

I am new to c++ and was trying develop a code for merge sort. I tested it with a sample array of size 5 but the answer put out by the code is not right. I can't figure what's going wrong. Here is my code:

我是 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);

}

The output is as follows:

输出如下：

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

I have seen some codes for merge sort implementation on stackoverflow but they use another temporary array, which I want to avoid.

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

Any help is greatly appreciated in sorting this issue.

非常感谢对这个问题进行排序的任何帮助。

回答by DrYap

The logic in your merge is wrong. During the merge phase you know that you have 2 sections of sorted numbers. When you compare and swap arr[start]and arr[mid]you will break the sorting of the top set of numbers if arr[start] > arr[mid+1]. The example shows a problem with your code as 2 will be left in the wrong place:

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

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

In order to keep the 2 sections sorted you would have to insert arr[start]in the correct place in the top set of numbers which would make the complexity worse than O(n lg n). This is the reason that a second array is used.

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

There are method which use smaller arrays than the original for merging, these have their overheads but don't compromise the complexity (or correctness). If you want an O(n lg n)in place sort then quicksort or heapsort is the way to go.

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

回答by Mr.Queries

Here is an implementation of merge sort for integer arrays:

这是整数数组的归并排序的实现：

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

And if you want to use it for other types, you can use in c++ templates like this:

如果你想将它用于其他类型，你可以在 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;
}

But with:

但与：

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

Output:

输出：

1
2
3
7
42

Hope I helped a little.

希望我有所帮助。

回答by j4nSolo

These lines seem wrong to me:

这些行对我来说似乎是错误的：

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

For swapping two indexes, that two must match.

为了交换两个索引，这两个索引必须匹配。

回答by harindersingh

This one worked PERFECTLY in codeblocks (compiler used : mingw)

这个在代码块中非常有效（使用的编译器：mingw）

#include <iostream>

using namespace std;

void merge(int*,int*,int,int,int);
void mergesort(int *a, int*b, int low, int high)
{
int pivot;
if(low<high)
{
    pivot=(low+high)/2;
    mergesort(a,b,low,pivot);
    mergesort(a,b,pivot+1,high);
    merge(a,b,low,pivot,high);
}
}
void merge(int *a, int *b, int low, int pivot, int high)
{
int h,i,j,k;
h=low;
i=low;
j=pivot+1;

while((h<=pivot)&&(j<=high))
{
    if(a[h]<=a[j])
    {
        b[i]=a[h];
        h++;
    }
    else
    {
        b[i]=a[j];
        j++;
    }
    i++;
}
if(h>pivot)
{
    for(k=j; k<=high; k++)
    {
        b[i]=a[k];
        i++;
    }
}
else
{
    for(k=h; k<=pivot; k++)
    {
        b[i]=a[k];
        i++;
    }
}
for(k=low; k<=high; k++) a[k]=b[k];
}

int main()
{
int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24};
int num;

num = sizeof(a)/sizeof(int);

int b[num];

mergesort(a,b,0,num-1);

for(int i=0; i<num; i++)
    cout<<a[i]<<" ";
cout<<endl;
} 

回答by Peyman Mahdavi

simple and completely working (by myself)

简单且完全有效（由我自己）

void MergeSort(int list[], int size)
{
    int blockSize = 1, p;
    int *a, *b;
    int *c = new int[size];
    do
    {
        for (int k = 0; k < size; k += (blockSize * 2))
        {
            a = &list[k];
            b = &list[k + blockSize];
            p = 0;
            for (int i = 0, j = 0; i < blockSize || j < blockSize;)
            {
                if ((j < blockSize) && ((k + j + blockSize) >= size))
                {
                    ++j;
                }
                else if ((i < blockSize) && ((k + i) >= size))
                {
                    ++i;
                }
                else if (i >= blockSize)
                {
                    c[p++] = b[j++];
                }
                else if (j >= blockSize)
                {
                    c[p++] = a[i++];
                }
                else if (a[i] >= b[j])
                {
                    c[p++] = b[j++];
                }
                else if (a[i] < b[j])
                {
                    c[p++] = a[i++];
                }
            }
            for (int i = 0; i < p; i++)
            {
                a[i] = c[i];
            }
        }
        blockSize *= 2;
    } while (blockSize < size);
}