CODEWITHSUNDEEP
c++algorithmsortingmergesort
Gurman8r
Gurman8r

Reputation: 311

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.

Upvotes: 0

Views: 1194

Answers (5)

Gurman8r
Gurman8r

Reputation: 311

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++;
    }
}

Upvotes: 1

rcgldr
rcgldr

Reputation: 28828

In the C++ merge function, the right half of L[] starts with mid + 1, so the second populate loop should be:

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

In the provided algorithm, indices go from 1 to n, so the first populate loop is TMP1[i] ← L[lowerBound + i - 1]. With C++, indices go from 0 to n-1, so the C++ first populate loop: tmp1[i] = L[lowerBound + i]; is correct, but the second loop needs to be changed to tmp2[j] = L[mid + j + 1]; .

Upvotes: 1

Yamaneko
Yamaneko

Reputation: 3563

Issue 1: Sentinels

infinity being commented out is one of the issues. 

// tmp1[size1] = (infinity?)
// tmp2[size2] = (infinity?)

It is used as a sentinel, so when you reach the last position of tmp1 (or tmp2), it'll ensure that you copy all the other elements from the other array, tmp2 (or tmp1). You can represent inf here using std::numeric_limits<T>::max().

@Petter made a good description of why this issue happens.

Issue 2: Initialization

Your other issue seems to be in the initialization, before merging your arrays:

int i = 1;
int j = i;

The pseudo-code is indexing from 1, while it should start from 0.

Issue 3: Indexing

As pointed out by @MarkRansom, the indexing range should be from 0 to size1, instead of size1 + 1.

tmp1[size1 + 1] = numeric_limits<T>::max();

Upvotes: 0

Mark Ransom
Mark Ransom

Reputation: 308121

It's a simple off by one error.

T * tmp1 = new T[size1 + 1]();
...
tmp1[size1 + 1] = numeric_limits<T>::max();
           ^^^

Array indexes go from 0 to n-1, not to n.

Upvotes: 3

Petter
Petter

Reputation: 1337

// tmp1[size1 + 1] = (infinity?)
// tmp2[size2 + 1] = (infinity?)

This is the part of the code that is breaking your merge, think about what would happen if you have two lists with 1 more element in them then they should, see: 

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

That means that they could look something like this for 2 values 

foo = [1,2,?]
bar = [3,4,?]

the questionmark will be some number but you have no way of knowing what, if you then run the comparison inside the loop a few times you will get to lets say i = 2, j == 0 for simplicity, now you try to do the comparison:

if (foo[2] <= bar[0])

and that's the same as

if (? <= 3)

meaning you have a undefined behavior, and what gets even worse is that you might go to i = 3 and start looking at random memory. So in conclusion, (infinity?) in some smart way.

Upvotes: 2

Related Questions