native sort vs algorithms quicksort in different node versions

algorithms.js_vs_native_sort.md

Check the conversation here https://twitter.com/felipernb/status/499661739244281859

As Felipe mentions native sort covers many edge cases so native method is less performant. However I get totally different results using node.js in different versions, check results_node_* files.

Some edge cases, see tests.js file:

• Sorting [1, null] produces different result in native than in algorithms.js.
• ['a', null, 'a'] produces inconsistent results in algorithms.js.

results_node_v0.10.30

$ node --version
v0.10.30

$ node -e "console.log(process.versions.v8)"
3.14.5.9

$ node sort.js
native sort x 28.35 ops/sec ±2.33% (51 runs sampled)
algorithms quicksort x 22.86 ops/sec ±3.16% (43 runs sampled)
Fastest is native sort

$ node sort.js
native sort x 28.73 ops/sec ±2.37% (52 runs sampled)
algorithms quicksort x 23.05 ops/sec ±3.02% (43 runs sampled)
Fastest is native sort

results_node_v0.11.13

$ node --version
v0.11.13

$ node -e "console.log(process.versions.v8)"
3.25.30

$ node sort.js
native sort x 17.61 ops/sec ±3.54% (33 runs sampled)
algorithms quicksort x 60.61 ops/sec ±1.60% (65 runs sampled)
Fastest is algorithms quicksort

$ node sort.js
native sort x 17.28 ops/sec ±4.08% (33 runs sampled)
algorithms quicksort x 60.74 ops/sec ±2.52% (65 runs sampled)
Fastest is algorithms quicksort

results_node_v0.8.28

$ node --version
v0.8.28

$ node -e "console.log(process.versions.v8)"
3.11.10.26

$ node sort.js
native sort x 15.73 ops/sec ±5.58% (30 runs sampled)
algorithms quicksort x 23.81 ops/sec ±2.28% (44 runs sampled)
Fastest is algorithms quicksort

$ node sort.js
native sort x 16.73 ops/sec ±6.35% (31 runs sampled)
algorithms quicksort x 23.57 ops/sec ±2.61% (44 runs sampled)
Fastest is algorithms quicksort

sort.js

var Benchmark = require('benchmark'),
    algorithms = require('algorithms');


var input = [];
    
for (var i = 0; i < 100000; i++) {
    var n = Math.random();
    input.push(n);
}

var suite = new Benchmark.Suite;

function cmp(a, b) { return a - b; };

suite
    .add('native sort', function() {
        input.slice(0).sort(cmp);
    })
    .add('algorithms quicksort', function() {
        algorithms.Sort.quicksort(input.slice(0));
    })
    .on('cycle', function(event) {
        console.log(String(event.target));
    })
    .on('complete', function() {
        console.log('Fastest is ' + this.filter('fastest').pluck('name'));
    })
    .run();

tests.js

var algorithms = require('algorithms'),
    assert = require('assert');

var example = [1, null];
try {
    assert.deepEqual(
        algorithms.Sort.quicksort(example.slice(0).sort()),
        example.slice(0).sort()
    );
} catch (e) {
    console.error(e.message || e);
}

var input = ['a', null, 'a'],
    lastResult;
while (true) {
    lastResult = algorithms.Sort.quicksort(input.slice(0).sort())
    try {
        assert.deepEqual(lastResult, input);
    } catch (e) {
        console.log(e.message || e);
        break;
    }
}