HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Mergesort performance in C

Submitted by: @import:stackexchange-codereview··
0
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 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.