views:

437

answers:

1

I have an assignment where I must output the number of comparisons that are made with the Merge sort algorithm, against an int list[1000] filled with random values (no duplicates).

My main question is, have I placed my comparisons++ count incrementer in the correct place.

Here is the code I am using

int Sort::MergeSort(int* list, int length)  {
    resetComparison();

    MergeSort(list, 0, length - 1);

    return comparisons;
}


void Sort::MergeSort(int* list, int first, int last) {
    if (first < last)   {
        int middle = (first + last) / 2;
        MergeSort(list, first, middle);
        MergeSort(list, middle + 1, last);
        merge(list, first, middle, middle + 1, last);
    }
}


void Sort::merge(int* list, int leftFirst, int leftLast, 
                 int rightFirst, int rightLast)  
{
    int* tempArray = new int[1000];
    int index = leftFirst;
    int saveFirst = leftFirst;

    while (leftFirst <= leftLast && rightFirst <= rightLast)    {
        if (list[leftFirst] < list[rightFirst]) {
            tempArray[index] = list[leftFirst];
            leftFirst++;
        }
        else    {
            tempArray[index] = list[rightFirst];
            rightFirst++;
        }

        index++;
        comparisons++;      // <<---count increment
    }

    while (leftFirst <= leftLast)   {
        tempArray[index] = list[leftFirst];
        leftFirst++;
        index++;
    }

    while (rightFirst <= rightLast) {
        tempArray[index] = list[rightFirst];
        rightFirst++;
        index++;
    }

    for (index = saveFirst; index <= rightLast; index++)
        list[index] = tempArray[index];

    delete [] tempArray;
}

Thanks!

A: 

It looks correct to me.

Jonathan Leffler
Thanks for the quick response!
dgilbert101