Merge sort implementation

Question

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:

#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.

Any help is greatly appreciated in sorting this issue.

Answer 1

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:

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.

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.

Answer 2

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:

    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.

Answer 3

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.

Answer 4

This one worked PERFECTLY in codeblocks (compiler used : 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;
} 

Answer 5

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