Merge Sort on a Array-Based List

[snowflake]

Here is the implement for the Merge Sort function in my ADT. I am able to get Bubble Sort and Quick Sort working, but I get a Heap Corruption Error.

template<class Type>
void listType<Type>::mergeSort()
{ 
    recursiveMergeSort(0, (maxSize - 1)); 
}//end of "mergeSort"


template<class Type>
void listType<Type>::recursiveMergeSort(int first, int last)
{ 
    int middle = 0;

        if(first < last)
            { 
                middle = ((first + last) / 2);
                recursiveMergeSort(first, middle);
                recursiveMergeSort((middle + 1), last);
            }

    mergeList(first, middle, (middle + 1), last);
}//end of "recursiveMergeSort"


template<class Type>
void listType<Type>::mergeList(int first1, int last1, int first2, int last2)
{

    int firstSublistIndex = first1; // set index for the 1st sublist
    int secondSublistIndex = first2; // set index for the 2nd sublist
    int bufferIndex = first1;
    Type *buffer;
    buffer = new Type[maxSize];

    while ((firstSublistIndex <= last1) && (secondSublistIndex <= last2))
        {
        if (list[firstSublistIndex] < list[secondSublistIndex])
            { 
                buffer[bufferIndex] = list[firstSublistIndex];
                ++firstSublistIndex;
            }
        else
            { 
                buffer[bufferIndex] = list[secondSublistIndex];
                ++secondSublistIndex; 
            }

        ++bufferIndex; 
        };


    while (firstSublistIndex <= last1)
        {
            buffer[bufferIndex] = list[firstSublistIndex];
            ++bufferIndex; 
            ++firstSublistIndex; 
        };

    while (secondSublistIndex <= last2)
        { 
            buffer[bufferIndex] = list[secondSublistIndex];
            ++bufferIndex; 
            ++secondSublistIndex; 
        };

    for (bufferIndex = first1; bufferIndex <= last2 ; ++bufferIndex)
        {
            list[bufferIndex] = buffer[bufferIndex];
        }

delete [] buffer;

} // end mergeList

[Rashakil Fol]

Put printfs up all over the place and track down the bug. It is hard and tedious to track down what you are doing here, especially when you haven't posted the class definition. (For example, what is 'maxSize'? If it's what I think it is, the name doesn't make sense. Why would your array have a maximum size (that's an unnecessary restriction :P) and don't you want _the_ size of the array, not some size it could theoretically attain? I guess you might just have a fixed size array, in which case a renaming of the variable would be in order.)

I think you meant to initialize bufferIndex to 0, not to first1. Other than that (and other than my general bitchiness) your code is well-written and very clear. Then again, you messed up the code tags... tsk tsk!

[snowflake]

I threw up some printf statements. The Heap was simply overflowing so I included the merge in the if statement

template<class Type>
void listType<Type>::recursiveMergeSort(int first, int last)
{ 
	int middle = 0;

		if(first < last)
			{ 
			middle = ((first + last) / 2);	
				recursiveMergeSort(first, middle);
				recursiveMergeSort((middle + 1), last);
				mergeList(first, middle, (middle + 1), last);
			}
}//end of "recursiveMergeSort"

I had the mergeList statement outside the if statement which caused the function to become infinitely recursive. My compiler didn't see anything until I forced the main function to fail and compiler.

Thanks for the help. I always miss the little things.