patterncMinor
Mergesort performance in C
Viewed 0 times
performancemergesortstackoverflow
Problem
I have two questions about my code:
- Are there any performance improvements in this implementation or generally (
register int?) that I could make?
- What could I improve in my coding style?
void mergesortArray(int data[], int amount){
if(amount == 1) return;
//Precomputing values
int sizeint = sizeof(int);
int amountLeft = amount / 2;
int amountRight = (amount % 2 == 0) ? amountLeft : (amountLeft + 1);
//Splitting the array in right and left
int *left = calloc(amountLeft, sizeint);
int *right = calloc(amountRight, sizeint);
if(left == NULL || right == NULL) return;
//Copying the splitted content
memcpy(left, data, amountLeft * sizeint);
memcpy(right, data + amountLeft, amountRight * sizeint);
//Recursive sorting the splitted arrays
mergesortArray(left,amountLeft);
mergesortArray(right,amountRight);
//Merging the numbers
int *pos1 = &left[0];
int *pos2 = &right[0];
int i = 0;
for(i = 0; i < amount; i++) {
if(*pos1 <= *pos2) {
data[i] = *pos1;
if (pos1 == &right[amountRight - 1])
break;
if(pos1 == &left[amountLeft - 1])
pos1 = &right[amountRight - 1];
else
pos1++;
}
else {
data[i] = *pos2;
if(pos2 == &right[amountRight - 1])
pos2 = &left[amountLeft - 1];
else
pos2++;
}
}
}Solution
The
Why
You should only need to allocate a single extra array for the merge.
When the amount left to sort is small (
Finally brace position on your else is a bit odd:
I'd expect either the opening braces to also be on its own line or else to be on the same as the closing brace of the if.
register keyword will do nothing. Current day compilers are smart enough to find a good register allocation themselves without you running in its way.Why
calloc? you initialize the values through memcpy anyway so no need for the zero initialization, malloc will work fine. Speaking of you need to free what you allocate otherwise you'll get a memory leak.You should only need to allocate a single extra array for the merge.
When the amount left to sort is small (
amount < 5) you can switch over to another sort that is more efficient for small numbers like insertion sort.Finally brace position on your else is a bit odd:
if(*pos1 <= *pos2) {
}
else {
}I'd expect either the opening braces to also be on its own line or else to be on the same as the closing brace of the if.
Code Snippets
if(*pos1 <= *pos2) {
}
else {
}Context
StackExchange Code Review Q#110987, answer score: 2
Revisions (0)
No revisions yet.