Array Merging Problem in MergeSort

[paulrishav93]

Write your question here.

  #include <iostream>
#include<cstdlib>
using namespace std;

void mergearray(int *a, int lo, int mid, int hi)
{
    int i=lo;
    int j=mid+1;                         //break array 'a' into two parts
    int k=0;                              //index for array 'b'

    int *b=new int[hi-lo+1];             //new array to store the merged array

    while(i<=mid && j<=hi)
    {
        if(a[i]<a[j])                          //merging
            b[k++]=a[i++];
        else
            b[k++]=a[j++];
    }

    while(i<=mid)                              //left-over elements
        b[k++]=a[i++];

    while(j<=hi)
        b[k++]=a[j++];

//array 'b' should be sorted right now. Copy elements to array 'a'

    for(i=hi;i>=lo;i--)
        a[i]=b[--k];

}

void mergesort(int *a, int lo, int hi)
{
    if(lo<hi)
    {
        int mid=((lo+hi)/2);
        mergesort(a,lo,mid);
        mergesort(a,mid+1,hi);
        mergearray(a,lo,mid,hi);
    }
}

int main()
{


    int a[]={2,5,4,1,23,34,45,12,68,35,46,15,67};

    mergesort(a,0,12);

    for(int i=0;i<13;i++)
    {
        cout<<a[i]<<" ";
    }
    
    return 0;
}

Instead of using

    for(i=hi;i>=lo;i--)
        a[i]=b[--k];

, if I use for(int i=lo;i<=hi;i++) a[i]=b[i];, the mergesort program does not work.

Why is it so? I am only trying to copy array b to array a.

[ne555]

Because you would be accessing `b' out of bounds.
The valid index for b goes from 0 to hi-lo.

Suppose hi=100, lo=90



Also, you are leaking memory