CODEWITHSUNDEEP
c++algorithmsortingmergesort
Amier
Amier

Reputation: 3

My Merge Sort algorithm don't get a correct answer

I an new to C++ and algorithm.I am confused at Merge Sort algorithm which I write. I don't know why the code don't get correct answer when it has no errors. In the code, I wanna to sort 5 numbers I input. but the sorted arrays doesn't print on screen. I want to know the problems in my code. Thanks a lot.

#include<iostream>
using namespace std;
int merge(int a[], int low, int mid, int high) {
    int h = low; int j = mid + 1; int k = low;
    int *b = new int[high - low + 1];
    while ((h <= mid) && (j <= high)) {
        if (a[h] < a[j])
            b[k++] = a[h++];
        else
            b[k++] = a[j++];

    }
    if (h > mid) {
        for (j; j <= high;++j)
            b[k++]=a[j];
    }
    if (j > high) {
        for (h; h <= mid; ++h)
            b[k++] = a[h];
    }
    for (int i = low; i <= high; ++i)
        a[i] = b[i];
    delete []b;
    return 0;
}
int MergeSort(int a[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    return 0;
}

int main() {
    int const n(5);
    int a[n];
    cout << "Input " << n << " numbers please:";
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    MergeSort(a, 0, n - 1);
    for (int i = 0; i <= n - 1; ++i)
        cout << a[i] << " ";
    cout << endl;
}

Upvotes: 0

Views: 79

Answers (2)

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

MergeSort function - assume low + 1 == high thus mid==low.

Recursive call with MergeSort(a, low, mid) will return immediately, while MergeSort(a, mid, high) will be passing again the same low and high - until your application will overflow the stack (and you'll post again a question on SO?)

merge function, assume low==3, mid==4, high==5.

You allocate a b[] of 3. So far so good.

But then you start with k=low (which is 3) and perform the assignment of b[k++] - already out of bounds even more at the next steps when you'll be writing at b[4] and b[5] (while b[0] and b[1] will stay untouched).

And so on (including for (int i = low; i <= high; ++i) a[i]=b[i]; )

What you probably want to do is to perform all the assignment to temp storage with a - low offset (b[k-low] followed by k++ at the end of the while cycle).

Upvotes: 1

James N
James N

Reputation: 84

I found only a minor problem. Try this simple fix.

for (int i = 0; i <= n - 1; ++i) {
        cout << a[i] << " ";
        cout << endl;
   }

Your code was missing the brackets in the for statement. This code works on my computer with this fix.

Upvotes: 0

Related Questions