Radix sort implementation 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 &lt; data.length; i++) {
        count[data[i]]++;
    }
    int cumulate = 0;
    for (int i = 0; i &lt; radix; i++) {
        for (int j = 0; j &lt; count[i]; j++)
            aux[cumulate + j] = i;
        cumulate = cumulate + count[i];
    }
    for (int i = 0; i &lt; aux.length; i++) {
        data[i] = aux[i];
    }
}
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 &lt; 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 &lt; radix; i++) {
    for (int j = 0; j &lt; count[i]; j++)
        aux[cumulate + j] = i;
    cumulate = cumulate + count[i];
}
for (int i = 0; i &lt; aux.length; i++) {
    data[i] = aux[i];
}



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


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



should be (with {} braces):

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


and just manipulate the data array directly

int cumulate = 0;
for (int i = 0; i &lt; radix; i++) {
    for (int j = 0; j &lt; 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 &lt; data.length; i++) {
    while (count[rad] == 0) {
        rad++;
    }
    count[rad]--;
    data[i] = rad;
}