radixsort
Blazingly fast radix sort in JavaScript for typed arrays.
npm install radixsort
Want to see pretty graphs? Log in now!
9 | downloads in the last month |
Last Published By | |
---|---|
Version | 1.0.1 last updated 2 years ago |
Keywords | radix sort, floating point |
Repository | git://github.com/jasondavies/radixsort.js.git (git) |
Homepage | https://github.com/jasondavies/radixsort.js |
Dependencies | None |
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
.