qqsort

quick, non-blocking quicksort

Traditional in-place quicksort, but yields to the event loop both while partitioning the array and between passes. Pivot picked at random.

I needed a sort function for real-world, large dataset use. It had to be non-blocking to support very large arrays and/or complex comparator functions, and had to allow for fatal errors in the comparator if the data was not sortable.

qqsort does not block the event loop, allows duplicate values, and catches errors thrown by the comparator.

    var qqsort = require('qqsort')

    var data = [2,3,1,4]
    qqsort(data, function(err) {
        // data => [1,2,3,4]
    })

    var data = [{a:2}, {a:3}, {a:1}, {a:4}]
    qqsort(data, function(a,b) { return a.a - b.a }, function(err) {
        // data => [{a:1}, {a:2}, {a:3}, {a:4}]
    })

API

qqsort( array, [comparator(e1, e2),] callback(err [,array]) )

Reorder the elements of the array in-place as established by the comparator function.

The comparator, if provided, will be passed array elements e1 and e2, and should return -1 if e1 is to precede e2, 1 if e1 is to follow e2, and 0 if they are the same. The default comparator is function(e1, e2) { return (e1 < e2) ? -1 : (e1 > e2) ? 1 : 0 }

The callback will be called with any error thrown by the comparator function and, for convenience, the modified input data array.

Changelog

• 1.0.9 - 35% faster and less blocking
• 1.0.5 - fail gracefully if not passed an array
• 1.0.4 - also support node v0.8
• 1.0.2 - yield more often
• 1.0.0 - initial version

Related Work

Searching for sort, qsort, quicksort, shellsort turns up lots of packages, but all seem to be pedagogic or experimental. The one I saw that took a callback still sorted synchronously internally, and used the callback only for call linkage.