CODEWITHSUNDEEP
c++algorithmmergemergesort
user2796815
user2796815

Reputation: 465

Mergesort giving weird answer

I've created this Mergesort function to sort a given array

#include <iostream>
using namespace std;
#include "sorting.h"



void mergesort_normal(int *A, int p, int r)
{
     if (p < r) {
      int middle = p + (r - p) / 2;
      mergesort_normal(A, p, middle);
      mergesort_normal(A, middle +1, r);
      merge_normal(A, p, middle, r);
    }
  }

void merge_normal  (int *A, int p, int mid, int r)
{
    int *helper = new int[r+1];
    int h = p;
    int i = r;
    int j = mid +1;
    int k = 0;


while((h<=mid)&&(j<=r))
{
    if(A[h]<=A[j])
    {
        helper[i]=A[h];
        h++;
    }
    else
    {
        helper[i]=A[j];
        j++;
    }
    i++;
}
 if(h>mid)
 {
    for(k=j;k<=r;k++)
    {
        helper[i]=A[k];
        i++;
    }
 }
 else
 {
    for(k=h;k<=mid;k++)
    {
        helper[i]=A[k];
        i++;
    }
 }
 for(k=p;k<=r;k++)
     A[k]=helper[k];
}


int main()
{
 int a[5] = {3,5,6,7,2};


 mergesort_normal(a,0,4);

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

 system("PAUSE");
 cout<<endl<<endl<<endl<<endl;
return 0;

}

I'm getting the output:

-842150451
-842150451
-842150451
-842150451
-842150451

Any idea on why this is happening? Also, how would I go about turning this into a Bitonic mergesort? Any help would be greatly appreciated!

Upvotes: 0

Views: 52

Answers (1)

Igor Tandetnik
Igor Tandetnik

Reputation: 52471

int *helper = new int[r+1];
int i = r;
helper[i]=A[h];
i++;

The first iteration of this (with i == r) is the first and the last that actually stays within boundaries of helper. After that, you are cheerfully overrunning the buffer.

Only the last element of helper (and a bunch of random memory past it) ever gets assigned to; the rest remains uninitialized.

Upvotes: 1

Related Questions