radixsort
v1.0.1
Published
Blazingly fast radix sort in JavaScript for typed arrays.
Downloads
102
Readme
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
.