c++ merge sort problem

[think13]

Ok, I have to make a c++ merge sort algorithm from some pseudocode that my teacher gave us for data structures class. Ive tested this algorithm in windows, it crashes the program with nothing. In ubuntu I get complicated backtracking and memory dump info. Can anyone see my problem?

void KAGSorting::mergeSort( ElementType list[], const int first, const int last )
{
    int middle;
    
    if( first != last )
    {
        middle = (first + last) / 2;
        mergeSort( list, first, middle );
        mergeSort( list, middle+1, last);
        merge( list, first, middle, last );
    }
    return;
}

void KAGSorting::merge( ElementType list[], const int first, const int middle, const int last )
{
        int f1, l1, f2, l2, fTemp;
        ElementType * temp = new ElementType[last + 1];

        f1 = first;
        l2 = middle;
        f2 = middle + 1;
        l2 = last;
        fTemp = f1;

        while(  ( f1 <= l1) && ( f2 <= l2) )
        {
                if( list[f1] < list[f2] )
                {
                        temp[fTemp] = list[f1];
                        f1++;
                }
                else
                {
                        temp[fTemp] = list[f2];
                        f2++;
                }
                fTemp++;
        }

        for( int index = f1; index <= l1; index++ )
        {
                temp[fTemp] = list[index];
                fTemp++;
        }

        for( int index = f2; index <= l2; index++ )
        {
                temp[fTemp] = list[index];
                fTemp++;
        }

        for( fTemp = first; fTemp <= last; fTemp++ )
        {
                list[fTemp] = temp[fTemp];
        }
        
        delete temp;
        return;
}

ElementType is an integer type. KAGSorting is the class all of the sorting algorithms are contained within.

[FoJaR]

Re: c++ merge sort problem

try getting rid of the square brackets when you're passing the ElementType:

void KAGSorting::mergeSort( ElementType list[B][color=red][][/color][/B], const int first, const int last )

you do it when you pass it in the other function too.

try that to start with.

[FoJaR]

Re: c++ merge sort problem

and it's been a while so i could be wrong... but i dont think you return in a void.

[think13]

Re: c++ merge sort problem

The brackets are the correct way to pass an array to a function. Its actually a pointer to the beginning of the array. My teacher wants us to return from void functions, as long as there is no value after return, its fine. I think my problem has something to do with memory leaks or going outside array boundaries.

[think13]

Re: c++ merge sort problem

After way too much work, I found the problem.

f1 = first;
l[B]2[/B] = middle;
f2 = middle + 1;
l2 = last;
fTemp = f1;

Should be

f1 = first;
l[B]1[/B] = middle;
f2 = middle + 1;
l2 = last;
fTemp = f1;

Arrgh!

[RandomPscho]

Re: c++ merge sort problem

Style always helps Use more meaningful variable names