Hacker News Reader

Comment by mbostock | Hacker News Reader

Yep. Typed arrays don't have a built-in sort method, and even the built-in array.sort is extremely slow. I ported Dart's dual-pivot quicksort implementation, which reduced the time to sort 1M floats from ~2.5s to ~350ms (timed in Node v0.6.2).

https://github.com/square/tesseract/blob/master/src/quicksor...

View on HN

For sorting numbers, you might also want to look at Radixsort.js, which takes O(n) time, although it isn't in-place like quicksort:

https://github.com/jasondavies/radixsort.js

I haven't finished implementing the Float64Array version, but it beats everything else I've compared it with even for relatively small sizes e.g. my benchmark is 65,536 floats and it's already around 2.5x faster than native sort (using Node.js)! Admittedly, Float32Array vs. native sorting of 64-bit floats is not a fair comparison, but you could argue that many applications would get away fine with 32-bit floats anyway. :)

Got inspired and it now supports Float64Array. :)

Good to know. I'll have to consider switching away from Underscore's sort, which is probably equally slow.

By the way, quicksort.js is code you wrote, right? I assume that's too nice and concise to be from the Dart generator...

Underscore doesn't have a "sort" apart from the native Array.prototype.sort, but it does have a "sortBy", which is something else entirely.

The sortBy method is just producing an integer array that is then sorted using each browser's implementation of Array.prototype.sort. Is that a proper reading of the code?

Bingo. You got it.

Right; I ported it from the Dart implementation, not from the generated JavaScript.

Reply on news.ycombinator.com