Radix sort implementation

Question

I have a problem where I need to sort an extremely large number of numbers but the numbers are in a narrow range (0..r-1) where r is typically around 10, and after googling around a bit it seemed like a good time to use radix sort. I have the following implementation below (I had to extract it out of a much larger program and simplify for illustration). It seems reasonably fast, but is there any other trick I can use to further speed it?

public static void sort(int[] data, int radix) {
    int aux[] = new int[data.length];
    int count[] = new int[radix];
    for (int i = 0; i < data.length; i++) {
        count[data[i]]++;
    }
    int cumulate = 0;
    for (int i = 0; i < radix; i++) {
        for (int j = 0; j < count[i]; j++)
            aux[cumulate + j] = i;
        cumulate = cumulate + count[i];
    }
    for (int i = 0; i < aux.length; i++) {
        data[i] = aux[i];
    }
}

Answer 1

Nice question.... but, you're not doing a Radix Sort, but instead you're doing a Counting Sort

As it happens, a counting sort is probably the best sort algorithm you could choose for this problem, so there's no problem in the basic code, just the name you have given it.

There's a significant optimization you can do though, which will save a bunch of memory.... you don't need the aux array at all.

The "counting" part of your code is great:

int count[] = new int[radix];
for (int i = 0; i < data.length; i++) {
    count[data[i]]++;
}

but the actual sorting is a problem. This code:

int aux[] = new int[data.length];
int cumulate = 0;
for (int i = 0; i < radix; i++) {
    for (int j = 0; j < count[i]; j++)
        aux[cumulate + j] = i;
    cumulate = cumulate + count[i];
}
for (int i = 0; i < aux.length; i++) {
    data[i] = aux[i];
}

has a few problems. First up, the bad 1-liner for-statement:

    for (int j = 0; j < count[i]; j++)
        aux[cumulate + j] = i;

should be (with {} braces):

    for (int j = 0; j < count[i]; j++) {
        aux[cumulate + j] = i;
    }

and just manipulate the data array directly

int cumulate = 0;
for (int i = 0; i < radix; i++) {
    for (int j = 0; j < count[i]; j++) {
        data[cumulate + j] = i;
    }
    cumulate = cumulate + count[i];
}

I would actually restructure that loop to make it more apparent how the indexing is done... I would have:

int rad = 0;
for (i = 0; i < data.length; i++) {
    while (count[rad] == 0) {
        rad++;
    }
    count[rad]--;
    data[i] = rad;
}

Answer 2

Three comments:

1. You are performing a lot of standard array manipulations for which there are implementations in the standard library. It may be faster to use this implementations; it will certainly be clearer. For example, this loop:

   for (int j = 0; j < count[i]; j++) aux[cumulate + j] = i;

can be replaced with this method call:

 Arrays.fill (aux, cumulate, cumulate + count[i], i);

Also the final copying of your output from aux to data can be done like:

 System.arraycopy (aux, 0, data, 0, aux.length);

2. Some of your naming is a little on the obscure side. I can figure out what "aux" and "cumulate" are, but using full, meaningful words would be better. "output" and "totalFilled" would be my choice for these.

3. It isn't clear why you're using the "aux" array at all. The results get stored in it, and then immediately copied to "data". Why not store then directly in "data" and avoid the extra copy?