C++: Merge Sort Merging Arrays

Question

When I run the code I get a lot of repeated numbers and/or large negatives that are usually there when you mess up adding things to you arrays. I believe the problem is when I am doing the merging itself.

void mergeSort( int list[], int lb, int ub )
{
    int mid;
    if ( lb < ub )
    {
        mid = (lb + ub) /  2;
        mergeSort(list, lb, mid);
        mergeSort(list, mid + 1, ub);
        myMerge(list, lb, mid , ub);
    }
}

template <class M>
void myMerge( M list[], int lb, int mid, int ub )
{
   int i, j;
   int size1 = mid - lb + 1;
   int size2 = ub - mid;

    M* tmpArray1 = new M[size1 + 1];
    M* tmpArray2 = new M[size2 + 1];

    for( i=0; i<size1; i++ )
    {
        tmpArray1[i] = list[lb + i - 1];
    }

    for( j=0; j<size2; j++ )
    {
        tmpArray2[j] = list[mid + j];
    }

    tmpArray1[size1 + 1] = INT_MAX;
    tmpArray2[size2 + 1] = INT_MAX;

    i = 0;
    j = i;

    for( int k=lb; k<ub; k++ )
    {
        if ( tmpArray1[i] <= tmpArray2[j] )
        {
            list[k] = tmpArray1[i];
                i++;
        }
        else
        {
            list[k] = tmpArray2[j];
            j++;
        }
    }
}

It's probably something stupid like an iteration problem... any ideas?

Answer 1

Your algorithm has a few problems.

First of all, it causes memory leaks, because it allocates arrays that it never deletes. A couple of delete[] instructions are needed to fix the problem.

Second, there are indexing errors: some indices get negative, which you surely do not want (e.g. when you do tmpArray1[i] = list[lb + i - 1];, because both lb and i can be 0).

Third, you are lacking a base step: you never swap the value of two elements. Your recursion step looks fine, but recursion has to end and do something concrete at some point (i.e. when your range spans only 2 elements). Your mergeSort() function splits the range and just recursively calls itself for the first and the second subrange, but does nothing with them when recursion gets to an end.

Fourth, you are not handling correctly the cases where the two sub-ranges have different sizes (one sub-range could be larger than the other one by one element).

And here is how you should fix your code (tested on GCC 4.7.2):

template <class M>
void myMerge( M arr[], int lb, int mid, int ub )
{
   int i, j;
   int size1 = mid - lb + 1;
   int size2 = ub - mid;

    M* tmpArray1 = new M[size1];
    M* tmpArray2 = new M[size2];

    for( i=0; i<size1; i++ )
    {
        tmpArray1[i] = arr[lb + i]; // THIS NEEDED FIXING
    }

    for( j=0; j<size2; j++ )
    {
        tmpArray2[j] = arr[mid + 1 + j]; // THIS NEEDED FIXING AS WELL (add +1...)
    }

    i = 0;
    j = i;

    for( int k=lb; k<=ub; k++ )
    {
        if (i == size1) // HANDLES THE CASE WHEN FIRST RANGE IS SMALLER
        {
            arr[k] = tmpArray2[j];
            j++;
        }
        else if (j == size2) // HANDLES THE CASE WHEN SECOND RANGE IS SMALLER
        {
            arr[k] = tmpArray1[i];
            i++;
        }
        else if ( tmpArray1[i] < tmpArray2[j] )
        {
            arr[k] = tmpArray1[i];
            i++;
        }
        else
        {
            arr[k] = tmpArray2[j];
            j++;
        }
    }

    delete[] tmpArray1; // IMPORTANT! DON'T FORGET TO RELEASE
    delete[] tmpArray2; // THE MEMORY YOU ALLOCATE...
}

void mergeSort( int arr[], int lb, int ub )
{
    if (ub - lb > 1)
    {
        int mid = (lb + ub) /  2;
        mergeSort(arr, lb, mid);
        mergeSort(arr, mid + 1, ub);
        myMerge(arr, lb, mid, ub);
    } 
    else // DON'T FORGET TO ADD YOUR BASE STEP! (sort a trivial range of 2 elements)
    {
        if (arr[ub] < arr[lb])
        {
            int tmp = arr[ub];
            arr[ub] = arr[lb];
            arr[lb] = tmp;
        }
    }
}

// SOME TESTING...

#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main()
{
    int numbers[] = { 8, 40, 1, 5, 0, 9, 6, 4, 3, -1, 5 };
    mergeSort(numbers, 0, 10);
    copy(begin(numbers), end(numbers), ostream_iterator<int>(cout, " "));
}

Answer 2

I'm assuming that the mergeSort code is correct, that means ub is supposed to be the last index of the range to be sorted. If that is not the case, mergeSort is wrongly implemented (and merge would still be, but in slightly different ways).

You access an element from before the range when populating tmpArray1:

for( i=0; i<size1; i++ )
{
    tmpArray1[i] = list[lb + i - 1];
}

The first element in the range is list[lb], not list[lb-1].

You're ignoringing one element at the end of the range when populating tmpArray2:

for( j=0; j<size2; j++ )
{
    tmpArray2[j] = list[mid + j];
}

That should be list[mid + 1 + j] there.

When merging, you don't merge all elements back:

for( int k=lb; k<ub; k++ )
{
    if ( tmpArray1[i] <= tmpArray2[j] )
    {
        list[k] = tmpArray1[i];
            i++;
    }
    else
    {
        list[k] = tmpArray2[j];
        j++;
    }
}

That should be k <= ub there in the loop control.

But, what rubs me most is

tmpArray1[size1 + 1] = INT_MAX;
tmpArray2[size2 + 1] = INT_MAX;

That is bound to fail if the array contains INT_MAX, or larger values if the element type is e.g. long long.

Using sentinel values to mark the end of the arrays is unsound, you should use the indices to detect it.

Answer 3

In this line:

    tmpArray1[i] = list[lb + i - 1];

Surely you mean this:

    tmpArray1[i] = list[lb + i];

Otherwise you are taking one value from outside the given merge bounds, which would explain the duplicated numbers. You don't use that logic when you write back to the list.