I'am doing a report about different sorting algorithms in C++. What baffles me is that my mergesort
seems to be slower than heapsort
in both of the languages. What I've seen is that heapsort
is supposed to be slower.
My mergesort
sorts an unsorted array with size 100000
at a speed of 19.8 ms meanwhile heapsort
sorts it at 9.7 ms. The code for my mergesort
function in C++ is as follows:
void merge(int *array, int low, int mid, int high) {
int i, j, k;
int lowLength = mid - low + 1;
int highLength = high - mid;
int *lowArray = new int[lowLength];
int *highArray = new int[highLength];
for (i = 0; i < lowLength; i++)
lowArray[i] = array[low + i];
for (j = 0; j < highLength; j++)
highArray[j] = array[mid + 1 + j];
i = 0;
j = 0;
k = low;
while (i < lowLength && j < highLength) {
if (lowArray[i] <= highArray[j]) {
array[k] = lowArray[i];
i++;
} else {
array[k] = highArray[j];
j++;
}
k++;
}
while (i < lowLength) {
array[k] = lowArray[i];
i++;
k++;
}
while (j < highLength) {
array[k] = highArray[j];
j++;
k++;
}
}
void mergeSort(int *array, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
mergeSort(array, low, mid);
mergeSort(array, mid + 1, high);
merge(array, low, mid, high);
}
}
See Question&Answers more detail:os