Counting sort implementation in C

Question

I've just implemented counting sort in C and would like to hear your opinions on it. As I'm usually being rather picky when rating other people's code, please go ahead and be picky, too -- I will try and justify my decisions but I'm thankful for any hints :)

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

/**
 * parses "[ a , b , c ]" into an array.
 * requirements:
 *  * first character must be a '['
 *  * subsequent characters until closing ']' must be `unsigned integer`,
 *    seperated by ','. Leading and trailing whitespace ignored.
 *
 * @return:
 *  * 0 on success
 *  * 1 if there was found an element > max
 *  * 2 if not len elements were found
 */
int parse_uint_array(size_t len, unsigned int maxval, unsigned int array[len],
        char *input)
{
    /* start at 1 to skip leading '[' */
    unsigned int pos = 1;
    for (size_t i = 0; i < len; i++)
    {
        int ccount;
        int n = sscanf(&input[pos], " %u , %n", &array[i],
                &ccount);
        if (n != 1 && i+1 < len) return 2;
        if (array[i] > maxval) return 1;
        pos += ccount;
    }
    return 0;
}

void print_uint_array(size_t len, unsigned int array[len])
{
    printf("[");
    for (size_t i = 0; i+1 < len; i++) {
        printf("%u, ", array[i]);
    }
    printf("%u]\n", array[len-1]);
}

/**
 * sorts an array of len size with maximum value maxval (can be less) which has
 * to be < UINT_MAX
 *
 * @returns
 *  * 1 if maxval+1 = 0, ie. usually maxval = UINT_MAX.
 *    This limitation is due to how counting sort works
 *  * 2 if malloc fails
 *  * 3 if an element is bigger than specified maxval
 */
int countsort_uint(size_t len, unsigned int maxval, unsigned int array[len])
{
    if (maxval+1 == 0) return 1;

    unsigned int *counts = malloc(sizeof(int)*(maxval+1));
    if (counts == NULL) {
        perror("malloc");
        return 2;
    }

    for (size_t i = 0; i < len; i++) {
        if (array[i] > maxval) return 3;
        counts[array[i]] += 1;
    }

    size_t pos = 0;
    for (size_t i = 0; i < (maxval+1); i++) {
        for (size_t j = pos; j < counts[i]+pos; j++) {
            assert(counts[i]+pos <= len);
            array[j] = i;
        }
        pos += counts[i];
    }
    assert(pos == len);

    free(counts);

    return 0;
}

int main(int argc, char *argv[])
{
    if (argc < 4) {
        fprintf(stderr, "not enough parameters supplied\n");
        return 1;
    }

    size_t len; if (sscanf(argv[1], "%zu", &len) != 1) return 2;
    if (len == 0) {
        fprintf(stderr, "length shouldn't be 0\n");
        return 4;
    }
    unsigned int max; if (sscanf(argv[2], "%u", &max) != 1) return 3;
    if (max+1 == 0) {
        fprintf(stderr, "maximum value < UINT_MAX\n");
        return 5;
    }

    unsigned int *array = malloc(sizeof(int)*len);
    if (array == NULL) {
        perror("malloc");
        return 6;
    }

    {
        int err;
        if ( (err = parse_uint_array(len, max, array, argv[3])) ) {
            fprintf(stderr, "parse_uint_array: returned %d\n", err);

            switch (err) {
            case 1:
                fprintf(stderr, "not all elements were less or equal than specified maximum\n");
                break;
            case 2:
                fprintf(stderr, "malformed array or less elements than specified\n");
                break;
            default:
                fprintf(stderr, "unknown error\n");
                break;
            }

            return 7;
        }
    }

    print_uint_array(len, array);

    {
        int err;
        if ( (err = countsort_uint(len, max, array)) ) {
            fprintf(stderr, "countsort_uint: returned %d\n", err);
            return 8;
        }
    }

    print_uint_array(len, array);

}

Answer 1

Input format

There are a few things I don't like about the way input is handled:

1. Having all of your input done via the command line is awkward. Suppose you wanted to try a test case of 10 million integers. How would you even do that? I propose that you read your input from stdin instead. That way you could just create a test input file and run your program like countsort < input.txt to test it.
2. I don't feel like the user should have to specify the maximum value as the second input value. Your program could just compute the maximum value as it reads in all the numbers. This would also allow you to remove some of the error checking you have where you test the array values against the maximum value.
3. I don't think there is a need for the [ and ] parts of the input, and also the comma separators. It would be simpler to just have the input be: the count n followed by n numbers without any extra brackets or commas.

Overflow in size computation

It looks like you took care of the special case where the maximum value was UINT_MAX, because in your call to malloc() you used the value max+1 and didn't want that to overflow to zero. However, there are many other ways to overflow in that same line:

unsigned int *counts = malloc(sizeof(int)*(maxval+1));

Suppose you were on a 32-bit platform with size_t being 32-bits wide, and suppose maxval were 0x40000000. The expression sizeof(int) * (maxval+1) would evaluate to 4 * 0x40000001 or just 4 because the result would be truncated to 32 bits. Note that 0x40000000 is just one example. Any value greater than or equal to 0x3fffffff would cause problems for this platform.

Bug: using uninitialized memory

You allocate your counts array using malloc(), but you never clear your counts array to 0 before you start to use it. So you could end up with garbage values for your counts. I would suggest using calloc() so that your allocated array is cleared to zero automatically. A side benefit to using calloc() is that it avoids your overflow problem because the arguments are split into a size and a count:

unsigned int *counts = calloc(maxval+1, sizeof(int));

Overflow in counts

If you were on a 64-bit platform with 64-bit size_t and 32-bit unsigned int, you could run into another type of overflow problem. Since your counts array is of type unsigned int (32-bit), your counts could overflow because your array could have more than 2^32 elements. For example, suppose your array had 5 billion instances of the number 5. Your program would overflow counts[5] and get the wrong count in the end.