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!