[C++] Radix sort – integers sorting

I have recently written article about counting sort, a linear complexity stable sorting algorithm: C++ counting sort implementation. Now I want to introduce you another fast sorting algorithm – radix sort. It is divided into two parts: one part that divides data to sort into small chunks and second part for real sorting. Radix sort is not an ideal algorithm for sorting integers (why you should use it when you have already counting sort?), but I think it is good example that shows an idea of positioning sorting.
Let’s see the implementation:

#include  // printf, puts
#include  // srand, rand
#include  // time, clock, time_t
#include  // memset
// every programmer should know memset ;)
#define MAX 6000000 // array size
#define RANGE 1000000 // range

void radix_sort(int *, int);

// implementations of this functions you can find in
// article describing counting sort
void generate(int*, int);
void write(int*, int);
void quick_sort(int *, int, int);
void counting_sort(int *, int, int);

int main(int argc, char** argv) {
        int* T = new int[MAX];
        time_t start, end;
        long dif;
        srand(time(NULL));

        puts("quicksort, O(nlog(n))");
        puts("counting sort, O(n)");
        // here similar code to below:

        puts("radix sort, O(n*k):");
        generate(T, MAX);
        start = clock();
        radix_sort(T, MAX);
        end = clock();
        dif = end - start;
        printf("%ld\n", dif / 1000);

        delete[] T;
        return 0;
}

// implementation very similar to counting sort -
// isn't it? ;)
// could be whatever function you like,
// but in this case we'll try counting sort.
// this example assumes, that processor
// uses little endian format
// int byte - which byte is it
void radix(int byte, int size, int *A, int *TEMP) {
        int* COUNT = new (int[256]);
        memset(COUNT, 0, 256 * sizeof(int));
        // multiplying by 8 to get the right bit shift
        // in next calculations.
        // 8 - the count of bits in byte.
        byte = byte << 3;
        // right shift
        // to achieve right byte.
        //  [3rd   ] [2nd    ] [1st   ] [0 byte ]
        // [++++++++ +++++++++ ++++++++ +++++++++]
        // most significant is 0-byte.
        // just counting sort:
        for (int i = 0; i < size; ++i)
                ++COUNT[((A[i]) >> (byte)) & 0xFF];
        for (int i = 1; i < 256; ++i)
                COUNT[i] += COUNT[i - 1];
        for (int i = size - 1; i >= 0; --i) {
                TEMP[COUNT[(A[i] >> (byte)) & 0xFF] - 1] = A[i];
                --COUNT[(A[i] >> (byte)) & 0xFF];
        }
        delete[] COUNT;
}

// in this case in radix sort we are sorting
// parts of an integer by bytes positions.
// assuming that values of A are greater
// than 0
void radix_sort(int *A, int size) {
        int* TEMP = new (int[size]);
        // in my processor sizeof(int) is 4
        for (unsigned int i = 0; i < sizeof(int); i += 2) {
                // even byte
                radix(i, size, A, TEMP);
                // odd byte
                // reuse of TEMP array
                radix(i + 1, size, TEMP, A);
        }
        delete[] TEMP;
}

Which prints:

quicksort, O(nlog(n))
1890
counting sort, O(n)
1190
radix sort, O(n*k):
880

As you see, if the range of values in array is very big radix sort can be even faster that counting sort! Moreover, execution time of radix sort is constant as long as you change range of values (not size of array!). It’s a very nice feature showing that the choice of algorithm is very important. Positioning sorting is much better in sorting strings, but it’s the topic for another article.
See also fast algorithms that sorts lists: C++ bucket sort implementation – list sorting.