radixsort

radixsort.js
============

Radix sort has linear time complexity, O(kN), where k is the number of
radices per value, and N is the number of values.

How is this possible? The theoretical lower bound of O(N log N) only applies
to comparison-based sorting algorithms, whereas radix sort doesn't actually
perform any comparisons on the input data.

Usage
-----

var sort = radixsort(),
data = new Float32Array([…]);

var sorted = new Float32Array(sort(data));

// You can also preallocate the output array…
var output = new Float32Array(data.length);
sort(data, output);

Informal Benchmark
------------------

The most common usage scenario for this will probably be sorting 32-bit floats
e.g. for geometry algorithms. My informal benchmark repeatedly sorts an array
of 65,536 random 32-bit floats.

Of course, the comparison is not entirely fair as JavaScript's native sort will
be sorting double-precision (64-bit) numbers, as this is all JavaScript
supports. But 32 bits is sufficient for most geometry algorithms, so the
comparison is reasonable.

* Radixsort.js: ~67 sorts per second.
* JavaScript native sort: ~26 sorts per second.

Radixsort.js is roughly 2.5x faster! The speed difference gets even larger
as you increase the input size.

To Do
-----

* Support Float64Array.