Search code examples
c++algorithmsortingmergesort

Merge Sort Not Working?

I'm having some trouble getting my Merge Sort function to work with the specifications given to me by my professor. Been staring at VS and Google for an eternity trying to figure this guy out.

The algorithm provided:

enter image description here

arrayFunctions.h

template<class T>
void printArray(T arr[], int numElements)
{
    cout << "(";

    for (int i = 0; i < numElements; i++)
    {

        cout << arr[i];

        if (i < numElements - 1)
            cout << ", ";
    }

    cout << ")" << "\n\n";
}

template <class T>
void setArray(T to[], T from[], int size)
{
    for (int i = 0; i < size; i++)
        to[i] = from[i];
}

template <class T>
void setArray(T to[], T from[], int size1, int size2)
{
    int size = size1;
    if (size2 < size1) size = size2;

    setArray(to, from, size);
}

main

const int NUM = 5;

int originalArray[NUM] = { 4, 2, 5, 3, 1 };
int newArray[NUM];

cout << "Original:\n";
printArray(originalArray, NUM); //prints an array with formatting

// Merge Sort
setArray(newArray, originalArray, NUM); //set's newArray to the same values of originalArray
mergeSort(newArray, 0, NUM - 1);

cout << "Merge Sort:\n";
printArray(newArray, NUM);

pause();

The output when running main is:

Original: (4, 2, 5, 3, 1 )

Merge Sort: (0, 0, 0, -33686019, 1)

merge:

template <class T>
void merge(T L[], int lowerBound, int mid, int upperBound)
{
    // Get size for new arrays
    int size1 = mid - lowerBound;
    int size2 = upperBound - mid;

    // Create Temporary Arrays
    T * tmp1 = new T[size1 + 1]();
    T * tmp2 = new T[size2 + 1]();


    // Populate both arrays from original
    for (int i = 0; i < size1; i++)
        tmp1[i] = L[lowerBound + i];

    for (int j = 0; j < size2; j++)
        tmp2[j] = L[mid + j];

    tmp1[size1] = numeric_limits<T>::max();
    tmp2[size2] = numeric_limits<T>::max();

    int i = 0;
    int j = i;

    for (int k = lowerBound; k < upperBound; k++)
    {
        if (tmp1[i] <= tmp2[j])
        {
            L[k] = tmp1[i];
            i++;
        }
        else
        {
            L[k] = tmp2[j];
            j++;
        }
    }

    delete[] tmp1;
    delete[] tmp2;
}

mergeSort:

template<class T>
void mergeSort(T L[], int lowerBound, int upperBound)
{
    if (lowerBound < upperBound)
    {
        int mid = (lowerBound + upperBound) / 2;

        mergeSort(L, lowerBound, mid);
        mergeSort(L, mid + 1, upperBound);

        merge(L, lowerBound, mid, upperBound);
    }
}

So... what am I doing wrong? A bump in the right direction would be GREATLY appreciated.

Solution

  • Sorry for forgetting to reply for nearly two weeks :/

    It was a few off by one errors, but I tracked them down and got it working. Thanks to everyone who helped.

    Changed

    int size1 = mid - lowerBound;
int size2 = upperBound - mid;

    to

    int size1 = mid - lowerBound + 1;
int size2 = upperBound - mid;

    Changed

    for (int j = 0; j < size2; j++)
    tmp2[j] = L[mid + j];

    to

    for (int j = 0; j < size2; j++)
    tmp2[j] = L[mid + j + 1];

    Changed

    for (int k = lowerBound; k < upperBound; k++)
{
    if (tmp1[i] <= tmp2[j])
    {
        L[k] = tmp1[i];
        i++;
    }
    else
    {
        L[k] = tmp2[j];
        j++;
    }
}

    to

    for (int k = lowerBound; k <= upperBound; k++)
{
    if (tmp1[i] <= tmp2[j])
    {
        L[k] = tmp1[i];
        i++;
    }
    else
    {
        L[k] = tmp2[j];
        j++;
    }
}