Merge Sort is going out of bounds

Vote count:

0

I'm implementing a merge sort and it works fine until it starts sorting the last end piece of the array. My input is: 5 8 85 9 78 34 2 6 31 56 7 16 89 476 84 8 22 65 900 76

The merge sorting returns these values: -33686019 2 5 6 7 8 9 16 22 31 34 56 65 76 78 84 85 89 476

As you can see, everything is offset by one placement in the array. Here is the relevant output from the test cout commands:

Final- Low: 19 High: 20
------
i3: 20 middle: 19 a: 19 b: 20
arrTemp[i2]: 76 arrTemp[i3]: -33686019 i2/i3: 19/20
Final- Low: 16 High: 20

Here are the functions:

void merge_sort(int arrTemp[],int r,int s)
{
    if(r<s)
    {
        int middle = (r+s)/2;
        merge_sort(arrTemp, r, middle);
        merge_sort(arrTemp,middle+1,s);
        cout << "Final- Low: " << r << " High: " << s << "\n" << "------\n";
        merge(arrTemp,r,s);
    }
}

void merge(int* arrTemp,int a, int b)
{
    int middle = (a+b)/2;
    int i1 = 0;
    int i2 = a;
    int i3 = middle + 1;
    cout << "i3: " << i3 << " middle: " << middle << " a: " << a << " b: " << b << "\n";
    int* temp = new int[b-a+1];

    while(i2 <= middle && i3 <= b)
    {
        if(arrTemp[i2] < arrTemp[i3])
        {           
            temp[i1] = arrTemp[i2];
            i1++;
            i2++;
        }
        else
        {
            cout << "arrTemp[i2]: " << arrTemp[i2] << " arrTemp[i3]: " << arrTemp[i3] << " i2/i3: " << i2 << "/" << i3 << "\n";
            temp[i1] = arrTemp[i3];
            i1++;
            i3++;
        }
    }
    while(i2 <= middle)
    {
        temp[i1] = arrTemp[i2];
        i1++;
        i2++;
    }
    while(i3 <= b)
    {
        temp[i1] = arrTemp[i3];
        i1++;
        i3++;
    }
    for(int i=a; i<=b;i++)
    {
        arrTemp[i] = temp[i-a];
    }
}

I'm not sure how to modify the code to prevent the sort from grabbing the max+1 placement value in the unsorted array.

asked 36 secs ago

Azreal

112