JuliaLang/julia — pull request #3952 by kmsquire (2013-08-06 06:09:04+00:00)
Title: RFC: RadixSort

This probably belongs in a package with #3825, but I wanted to put it here to get some feedback, and to see if there's a reason for it in base.

This is a fairly fast implementation of radix sort. Many of the ideas were inspired by http://www.stereopsis.com/radix.html:

* histogramming all radixes simultaneously
* 11-bit radixes, rather than 8-bit, to reduce the number of passes through the data
* bit twiddling for signed integers and floating point numbers mapping them to unsigned integers, while maintaining sort order (see the `uint_mapping` function)

Additionally, one optimization occurs during the sort phase, where an extra comparison is done up front to see if any sorting is needed for the current radix; if none is needed, that iteration is skipped. This is useful for sorting, e.g., 64-bit integers with small values/ranges, as many of the radixes will be zero for all numbers involved.

After some work, the results is quite performant, with a few caveats/limitations. Benefits include

1) it is especially fast at sorting smaller Int sizes (32-bit and smaller), often 2-4x faster than `QuickSort` (which is already a pretty fast implementation), and generally faster even for 64-bit numbers when the data is random
2) it is a stable sort
3) it's integrated with the current sorting framework, and can work with all standard `Orderings` except `Lt`.

Limitations:

1) it's limited to bits types: all sizes of `Int`, `Uint`, and `Float32/Float64`; no direct sorting of Strings
2) it will work with functions of non-bit types (eg., `sort!(a::Array{String}, by=length)` as long as the function produces a bits type; however the function call overhead is currently pretty high
3) in the same vein, it works with `sortperm`, with some overhead; this can still be faster than other algorithms for smaller data types
3) it has an up-front overhead which makes it slower than the other sorts for lists with less than ~2^13 (8192) values, give or take, depending on the machine. Larger than that, it is generally faster than all other sorts (in Julia) for straight lists of Ints/Floats
4) For 128-bit numbers, it is quite slow (assuming the high order bits are not empty). This is not surprising, since the run time is proportional to the size of the items being sorted, and 128-bit numbers are big
5) It uses O(N) memory (like `MergeSort`), which affects performance at some point depending on list and machine being used

You can see a comparison of all sorts in the (SortPerf.jl package)[https://github.com/kmsquire/SortPerf.jl]. The README has a table with a summary suggesting when each algorithm should be used, and sortperf.pdf shows a comparison of all of the different sort algorithms run on various tests. (Note that most of the tests were originally written to show off `TimSort`, and have some structure that other sorts (but not radix sort) can take advantage of. `RadixSort` does come out on top sorting random lists, as well, as large lists with only a few unique values.)

Finally, I had to work around some type inference limitations for the `uint_mapping` function (look for "manually inlined" comments). I'll file those issues separately.

Comments/suggestions on the implementation or what to do with it are welcome.

CC: @StefanKarpinski