What is wrong with my C++ merge sort program?

Question

I'm stuck at an impass with this implementation. My n2 variable is being overwritten during the merging of the subarrays, what could be causing this? I have tried hard-coding values in but it does not seem to work.

#include <iostream>
#include <cstdlib>
#include <ctime> // For time(), time(0) returns the integer number of seconds from the     system clock
#include <iomanip>
#include <algorithm> 
#include <cmath>//added last nite 3/18/12 1:14am

using namespace std;

int size = 0;

void Merge(int A[], int p, int q, int r)
{
    int i,
        j,
        k,
        n1 = q - p + 1,
        n2 = r - q;

    int L[5], R[5];

    for(i = 0; i < n1; i++)
        L[i] = A[i];

    for(j = 0; j < n2; j++)
        R[j] = A[q + j + 1];

    for(k = 0, i = 0, j = 0; i < n1  && j < n2; k++)//for(k = p,i = j = 1; k <= r; k++)
    {
        if(L[i] <= R[j])//if(L[i] <= R[j])
        {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}

void Merge_Sort(int A[], int p, int r)
{
    if(p < r)
    {
        int q = 0;
        q = (p + r) / 2;
        Merge_Sort(A, p, q);
        Merge_Sort(A, q+1, r);
        Merge(A, p, q, r);
    }
}

void main()
{
    int p = 1,
        A[8];

    for (int i = 0;i < 8;i++) {
        A[i] = rand();
    }
    for(int l = 0;l < 8;l++)
    {
        cout<<A[l]<<"  \n";
    }
    cout<<"Enter the amount you wish to absorb from host array\n\n";
    cin>>size;
    cout<<"\n";
    int r = size; //new addition
    Merge_Sort(A, p, size - 1);

    for(int kl = 0;kl < size;kl++)
    {
        cout<<A[kl]<<"  \n";
    }

}

Answer 1

I had used the similar Merge function earlier and it doesn't seem to work properly. Then I redesigned and now it works perfectly fine. Below is the redesigned function definition for merge function in C++.

void merge(int a[], int p, int q, int r){
    int n1 = q-p+1;             //no of elements in first half
    int n2 = r-q;               //no of elements in second half
    int i, j, k;

    int * b = new int[n1+n2];   //temporary array to store merged elements

    i = p;
    j = q+1;
    k = 0;
    while(i<(p+n1) && j < (q+1+n2)){     //merging the two sorted arrays into one
        if( a[i] <= a[j]){
            b[k++] = a[i++];
        }
        else 
            b[k++] = a[j++];
    }

    if(i >= (p+n1))         //checking first which sorted array is finished
        while(k < (n1+n2))      //and then store the remaining element of other 
            b[k++] = a[j++];    //array at the end of merged array.
    else
        while(k < (n1+n2))
            b[k++] = a[i++];

    for(i = p,j=0;i<= r;){      //store the temporary merged array at appropriate  
        a[i++] = b[j++];        //location in main array.
    }

    delete [] b;
}

I hope it helps.

Answer 2

What tools are you using to compile the program? There are some flags which switch on checks for this sort of thing in e,.g. gcc (e.g. -fmudflap, I haven't used it, but it looks potehtially useful).

If you can use a debugger (e.g. gdb) you should be able to add a 'data watch' for the variable n2, and the debugger will stop the program whenever it detects anything writing into n2. That should help you track down the bug. Or try valgrind.

A simple technique to temporarily stop this type of bug is to put some dummy variables around the one getting trashed, so:

int dummy1[100];
int n2 = r - q;
int dummy2[100];

int L[5], R[5];

Variables being trashed are usually caused by code writing beyond the bounds of arrays. The culprit is likely R[5] because that is likely the closest. You can look in the dummies to see what is being written, and may be able to deduce from that what is happening.

ANother option is to make all arrays huge, while you track down the problem. Again set values beyond the correct bounds to a known value, and check those values that should be unchanged.

You could make a little macro to do those checks, and drop it in at any convenient place.

Answer 3

void Merge(int A[], int p, int q, int r)
{
    int i,
        j,
        k,
        n1 = q - p + 1,
        n2 = r - q;

    int L[5], R[5];

    for(i = 0; i < n1; i++)
        L[i] = A[i];

You only allocate L[5], but the n1 bound you're using is based on inputs q and p -- and the caller is allowed to call the function with values of q and p that allow writing outside the bounds of L[]. This can manifest itself as over-writing any other automatic variables, but because it is undefined behavior, just about anything could happen. (Including security vulnerabilities.)

I do not know what the best approach to fix this is -- I don't understand why you've got fixed-length buffers in Merge(), I haven't read closely enough to discover why -- but you should not access L[i] when i is greater than or equal to 5.

This entire conversation also holds for R[]. And, since *A is passed to Merge(), it'd make sense to ensure that your array accesses for it are also always in bound. (I haven't spotted them going out of bounds, but since this code needs re-working anyway, I'm not sure it's worth my looking for them carefully.)