Why is my merge sort not working?

Question

It compiles fine, but when it runs, it adds random high numbers to the list, as well as duplicates of existing numbers. I've had a couple of people look over this, and none of them can figure it out.

void mergeSort(int list[], int length) {
    recMergeSort(list, 0, length - 1);
}

void recMergeSort(int list[], int first, int last) {

    if (first < last) {
        int mid = (first + last) / 2;
        recMergeSort(list, first, mid);
        recMergeSort(list, mid + 1, last);
        merge(list, first, last, mid);
    }
}

void merge(int list[], int first, int last, int mid) {

    int arraySize = last - first + 1;
    int* tempList = new int[arraySize];
    int beginPart1 = first;
    int endPart1 = mid;
    int beginPart2 = mid + 1;
    int endPart2 = last;


    int index = beginPart1;


    while (beginPart1 <= endPart1 && beginPart2 <= endPart2) {
        if (list[beginPart1] < list[beginPart2]) {
            tempList[index] = list[beginPart1];
            beginPart1++;
        }
        else {
            tempList[index] = list[beginPart2];
            beginPart2++;
        }
        index++;
    }

    while (beginPart1 <= endPart1) {
        tempList[index] = list[beginPart1];
        index++;
        beginPart1++;
    }

    while (beginPart2 <= endPart2) {
        tempList[index] = list[beginPart2];
        index++;
        beginPart2++;
    }


    for (int i = first; i <= last; i++) {
        list[i] = tempList[i - first];
    }

    delete[] tempList;
}

Answer 1

In function merge(), you're incorrectly calculating the index variable:

Assuming begin = 10, mid = 14, end = 19 (for a total array size of 0 .. 19, and you're recMergeSort()ing the higher half), your index = 10, but the tempList array is indexed 0..9 (because arraySize = last - first + 1 == 10).

So you're overflowing your tempList array, and when you "merge", you get data corruption.

Fix your index variable to be 0-based (rather than beginPart1 based).

Answer 2

If I run this in C# I get an IndexOutOfRangeException on the following line:

                    tempList[index] = list[beginPart1];

I reckon if you trace it through you are probably running off the end of a buffer somewhere hence the random numbers.

Answer 3

I think problem is here:

int index = beginPart1;

It should be

int index = 0;