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.
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);
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.
- Radixsort.js: ~67 sorts per second.
Radixsort.js is roughly 2.5x faster! The speed difference gets even larger as you increase the input size.