Erik Gorset's Blog

---

Is radix sort faster than quicksort for integer arrays?

discussion at reddit

There are plenty of misconceptions and confusion over radix sort on the internet. The wikipedia article is messy and unclear, and focuses more on trying to explain the philosophy (for lack of a better word) than the characteristics and capabilities of radix sort.

In Engineering radix sort McIlroy et al. discusses how radix sort can be used successfully to sort arrays of strings, using the American Flag Sort variant. The algorithm can be adapted into a high performance sort algorithm for integers, as shown by Birkeland in Searching large data volumes with MISD processing. But how fast is it? Let's find out!

Implementation

The implementation proved to be surprisingly simple. The algorithm works by first counting the number of elements for each base256 digit. Then it swaps elements for each digit in-place until all is in place. Finally, it will recursively sort the next digit for all digits. A simple optimization is performed by using insertion sort when the number of elements left to sort is low.

The complexity is O(kN) with k = 4 for 32-bit integers. The digits are sorted in MSD order.

It's important to note that complexity analysis of e.g. quicksort assumes that each comparison is O(1), which isn't true in practice on real hardware nor correct in theory when considering variable sized elements. Radix sort is asymptotically better than comparison based algorithms, but the question is how costly the bookkeeping is.

Benchmark

Java's Arrays class contains optimized versions for integers of different sizes, so it should be fair to compare our "specialized" integer sorter to the "built-in" quicksort based Arrays.sort(int[]). The benchmark will be somewhat unscientific, only using random data, but should hopefully be sufficient to answer the question: Is radix sort faster than quicksort for integer arrays?

Hardware:

Kernel: Linux 2.6.38-020638rc3-generic #201102010912 SMP
CPU: Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
RAM: 16GB

Language options:

C++: -O3 radix.cc -o radix
Java: -Xmx10G

The benchmark shows the MSB in-place radix sort to be consistently over 3 times faster than quicksort for large arrays. It's also significantly faster for smaller arrays, but with more variable results probably due to various caching effects.

It's interesting to see that there's no significant difference between the Java and C for large arrays. The difference in smaller arrays is most likely due to conditions in the benchmark code, however, the JIT's warmup time is indeed included, and java is actually faster!

Radix.sort and Arrays.sort is implemented in Java, while std::sort, qsort and radix_sort in C++.

C++ and Java version of radix sort is indistinguishable for large arrays.

Conclusion

For integer arrays, radix sort beats quicksort in theory, actual speed, algorithmic clearity and readability.

for (x=0; x<256; ++x) {
    while (pointer[x] != last[x]) { // continue until all elements for the bucket have been found
        value = array[pointer[x]];
        y = (value >> shift) & 0xFF;
        while (x != y) { // swap until the cycle is complete
            temp = array[pointer[y]];
            array[pointer[y]++] = value;
            value = temp;
            y = (value >> shift) & 0xFF;
        }
        array[pointer[x]++] = value;
    }
}

Resources

The source code. Drop me a note if you have any comments or find any bugs. Feel free to rerun the benchmark yourself.

Searching large data volumes with MISD processing. The doctorate thesis describing (among other things) the radix sort implementation used here, which was developed for speeding up search queries in the old AllTheWeb search engine core. It has an in-depth analysis and a discussion of practical aspects such as partial sorting.

Parallel query evaluation on multicore architectures. A master's thesis mentioning the use of radix sort in Vespa - the vertical search platform used by Yahoo!, which also is descendent from AllTheWeb through their acquisition of the web search department (via Overture Services, Inc.) of Fast Search & Transfer (the rest of the company was later acquired by Microsoft).

---

Posted 2011-04-26, by Erik Gorset, Oslo, Norway.