Is there a good library for sorting a large array of numbers in C?

Question

If I have a large array of integers or floats, what is a good algorithm/ implementation for sorting (in C)?

It is a bit late in the game for an edit... but I am looking for correctness and speed.

Answer 1

For sorting arrays of numbers, consider a radix sort algorithm. When properly engineered, these sorts should provide better performance than GLIBC qsort().

The usort library contains type-specific implementations for all the major C numeric types.

http://bitbucket.org/ais/usort/wiki/Home

The speed advantage of radix sort over GLIBC qsort is about 2.5x for double precision floating point numbers at N=1000000 on my 64 bit intel laptop. However, as N grows the advantage should be even greater since radix sort is a linear time algorithm requiring constant number of passes through the data.

For very small N, the same code dispatches to an introsort or insertion sort.

Answer 2

qsort() from the standard library is a good'un.

The comparison functions would be trivial for these cases:

int cmp_int(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;

    if (*ia < *ib)
        return -1;

    if (*ia > *ib)
        return 1;

    return 0;
}

int cmp_float(const void *a, const void *b)
{
    const float *fa = a;
    const float *fb = b;

    if (*fa < *fb)
        return -1;

    if (*fa > *fb)
        return 1;

    return 0;
}

(EDIT: The version of these based on subtracting b from a relies on signed overflow behaviour, so it's not a good idea.)

Answer 3

It's never a bad idea to use qsort... unless you know something about the numbers.

You've tagged with radix sort. How much memory are you prepared to invest? Are the numbers inside a specific range? Do they have properties that makes radix sorting feasible?

Unless you want to use a lot of memory, qsort is a great option.

Answer 4

Given a huge amount of RAM we're getting nowadays, the following set sort is possible: mark the bit in a huge RAM bit array for each number you have, then read them off back by scanning the RAM. Lots of hardware-specific optimizations can be applied for the mark and scan phases.