Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

This is a mergesort implementation I wrote, trying to get back into C.

I am not so much interested in feedback on the optimality of the algorithm (as I could read up countless articles i'm sure), but deep criticism of my style would be greatly appreciated.

(The code works btw)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void mergesort_recurse(int* in_array, int i, int j);
void merge(int* array, int left, int centre, int right);


void mergesort(int* in_array, int len) {
    mergesort_recurse(in_array, 0, len);
}


void mergesort_recurse(int* in_array, int left, int right) {

    int length = right-left;

    /*Base case: There are only two elements - Compare them and swap if
      necessary.*/
    if(length == 2) {
        if(in_array[left] > in_array[right-1]) {
            int temp = in_array[right-1];
            in_array[right-1] = in_array[left];
            in_array[left] = temp;
        }
    }

    /*Leaves of lenth 1 can be ignored as they are already "sorted"*/
    else if(length > 1){

        /*Split into two and sort recursively.*/
        int centre = left + length / 2;

        mergesort_recurse(in_array, left, centre);
        mergesort_recurse(in_array, centre, right);
        merge(in_array, left, centre, right);
    }
}

void merge(int* array, int left, int centre, int right) {

    /*Establish the initial indexes of the left and right sides of the two
      "halves" to be merged.*/
    int l = left;
    int r = centre;
    int length = right-left;

    /*A temporary array to hold the merged data - this implementation is not
      in-place*/
    int* tmp = malloc(length * sizeof(int));


    /*Iterate over the length of the merge.*/
    int i;
    for(i = 0; i < length; i++) {

        if(r==right){
            /*If the right index has reached the right hand end of the data, the
              remaining elements can be dumped in from the LHS.*/
            memcpy(tmp+i, array+l, (length-i)*sizeof(int));
            break;
        }

        else if (l==centre) {
        /*Conversely if the left index has reached the LHS end, the
              remaining elements can be dumped in from the RHS.*/
            memcpy(tmp+i, array+r, (length-i)*sizeof(int));
            break;
        }

        else if(array[l] < array[r]) {
        /*Otherwise add from the left or right by comparison.*/
            tmp[i] = array[l];
            l++;
        }

        else {
            tmp[i] = array[r];
            r++;
        }
    }

    /*Finally memcpy the temp array into the target.*/
    memcpy(array+left, tmp, length*sizeof(int));
    free(tmp);
}
share|improve this question
add comment

2 Answers 2

I can't fault too much here, it's generally looking pretty reasonable. I think the first point below is the most important, depending on how much experience you have with C, the second may or may not make much sense.

Information Hiding

Firstly, you should split this up into separate .h and .c files; perhaps you've already done this but just pasted them together for this post. Either way, if you want to reuse this, you'll need to put your function prototypes into a header file to #include.

When you do this, you should give internal only functions (that is, functions you don't want your users to call directly) internal linkage. Hence your two functions:

void mergesort_recurse(int* in_array, int i, int j);
void merge(int* array, int left, int centre, int right);

should be prefaced with static:

static void mergesort_recurse(int* in_array, int i, int j);
static void merge(int* array, int left, int centre, int right);

So your header will look something like:

#ifndef MERGESORT_H_
#define MERGESORT_H_

void mergesort(int *in_array, int len);

#endif //MERGESORT_H_

And the static function prototypes go in the .c file:

static void mergesort_recurse(int* in_array, int i, int j);
static void merge(int* array, int left, int centre, int right);

This prevents anyone but the implementer from calling merge or mergesort_recurse. This allows you to safely modify any static functions and know that they won't be utilized in any user code - their interfaces can freely change and it won't break things - they're effectively private functions, in object-oriented terms.

Generic Sorting

You say you're trying to get back into C, and I'm not sure how well you knew the language before, but generally things like sorting routines will be generic. This can be somewhat complex, but I'll run through what you'd need to change if you wanted to allow sorting any type.

Firstly, all our int * become void *. We'll also need to add a parameter specifying the size of the type we're actually passing in.

void mergesort(void *in_array, int len, size_t el_size);

Next step is to abstract away how comparison is done: instead of simply using < or >, we'll pass in a function pointer which we can use as a comparison function: this has the signature:

int (*compare)(const void*, const void*);

That's pretty ugly though, so let's make a typedef for it:

typedef int (*cmp_t)(const void*, const void*);

We'll also do the same thing for swapping two values: this will be used to replace

int temp = in_array[right-1];
in_array[right-1] = in_array[left];
in_array[left] = temp;

Again, with a typedef:

typedef void (*swap_t)(void *, void *);

Our header now looks like:

#ifndef MERGESORT_H_
#define MERGESORT_H_

typedef int (*cmp_t)(const void*, const void*);
typedef void (*swap_t)(void *, void*);

void mergesort(void *in_array, int len, size_t el_size, cmp_t, swap_t);

#endif //MERGESORT_H_

And our in .c:

static void mergesort_recurse
(void* in_array, int i, int j, size_t el_size, cmp_t, swap_t);

static void merge(void *array, int left, int centre, int right, size_t el_size, cmp_t);

The implementation can is still fairly similar, but working with void* makes things a bit messier. Instead of if(in_array[left] > in_array[right-1]) we'll need to call our comparison function, and do a bunch of mucking around with casts:

compare(((char *)in_array + (left * el_size)), ((char *)in_array + (right - 1)*el_size)) > 0)

Hrm, yuck, that's pretty ugly. Let's make a function that can do all of this casting and index calculating for us:

In our .c file:

static void* get_pos(void *array, int index, size_t el_size)
{
    return ((char *)array + (index * el_size));
}

The only other thing that needs to be changed in this function is passing through function pointers to the other functions:

mergesort_recurse(in_array, left, centre, el_size, compare, swap);
mergesort_recurse(in_array, centre, right, el_size, compare, swap);
merge(in_array, left, centre, right, el_size, compare);

In merge, all the calls to memcpy will have to change a little bit, for example:

memcpy(get_pos(tmp, i, el_size), get_pos(array, r, el_size), (length-i) * el_size);

Doing all of this allows the user to sort whatever they want - integers, doubles, structs, whatever - as long as they provide their own comparison and swap functions:

int compare_i(const void *a, const void *b)
{
    int x = *((int *)a); 
    int y = *((int *)b);
    if(x == y) return 0;
    if(x < y) return -1;
    return 1;
}

void swap_i(void *a, void *b)
{
    int temp = *(int *)a;
    *((int *)a) = *((int *)b);
    *((int *)b) = temp;
}

So our mergesort call would look something like:

int x[] = {5, 8, 2, 3, 1, 7, 10};
mergesort(x, 7, sizeof(int), compare_i, swap_i);

If the above is all very confusing, I apologise, but hopefully it'll give you something to look back on when you get into the hairier parts of C. The standard library qsort uses these techniques to be generic sorting routine as well, so understanding this will help with understanding parts of the standard library.

share|improve this answer
1  
+1, but one tiny nitpick: Why declare the static functions in the header? That completely breaks the idea of encapsulating them from the calling code. Also, if some consuming code wanted to have a function called merge with the same signature, it now can't without it being forced to be static (the chances of that happening are tiny, but the theory should apply). –  Corbin Jan 30 '13 at 6:13
    
@Corbin You're completely right, I had a brainfart there. I've updated my post. –  Yuushi Jan 30 '13 at 6:24
    
That's great, thanks very much! I just had one question: Why would I need to genericise the swapping? Is there a situation where it would be something other than swapping their places in the array? –  trideceth12 Jan 30 '13 at 11:19
    
You don't have to genericise the swap, you could do the same thing with a few calls to memcpy. I just added it in there because I think it's slightly cleaner. It's certainly not an essential part, however. –  Yuushi Jan 30 '13 at 13:50
    
+1 for allowing the user to pass in a comparison function. But if you do this, you should also allow the user to supply an environment void *env which gets passed as a third argument to the comparison function each time it is called. (This works around C's lack of closures.) –  Gareth Rees Jan 31 '13 at 17:36
show 1 more comment

I can't compete with the answer you got from @Yuushi but I have some nit-picking and pedantry to add.

  • C functions usually start with the opening { in column 0.
  • functions are best ordered so that local prototypes are unnecessary - i.e. in reverse order of use.
  • I prefer keywords (if, for, while etc) to be followed by a space.
  • I prefer int *var; to int* var;. Consider int* var1, var2; - var2 is not a pointer.
  • there is some extra vertical spacing that, to me, is undesirable
share|improve this answer
    
Thanks for the feedback! Tbh I thought I was following Kernighan and Ritchie, placing the { at the end of the definition, but having bothered to pull the book off the shelf I see that they don't do that for functions. Your tip on keywords is also in line with K&R. I also accept your reasoning on pointer declarations. However I am not decided (either way) on the issue of vertical spacing. Sometimes I philosophise that the empty space is the most important factor contributing to readablity (like in Chinese art and calligraphy). One day I'll be convinced one way or the other. –  trideceth12 Jan 31 '13 at 4:34
    
The int *var vs int* var only really helps the argument to not put more than 1 declaration per line. I don't think it matters too much either way - actually, when I write C I'll use int *var, when writing C++, int* var. The argument is that the type is int* so the * should go with the type, but that's also not terribly convincing. –  Yuushi Jan 31 '13 at 6:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.