sort vs binsearch

test.js

/* eslint-env browser */
/* eslint no-bitwise: 0, no-console: 0*/

'use strict';

function binSearch(haystack, needle, comparator, low, high) {
    var mid, cmp;

    if (low === undefined) {
        low = 0;
    } else {
        low = low | 0;
        if (low < 0 || low >= haystack.length) {
            throw new RangeError('invalid lower bound');
        }
    }

    if (high === undefined) {
        high = haystack.length - 1;
    } else {
        high = high | 0;
        if (high < low || high >= haystack.length) {
            throw new RangeError('invalid upper bound');
        }
    }

    while (low <= high) {
        /* Note that "(low + high) >>> 1" may overflow, and results in a typecast
         * to double (which gives the wrong results). */
        mid = low + (high - low >> 1);
        cmp = +comparator(haystack[mid], needle, mid, haystack);

        /* Too low. */
        if (cmp < 0.0) {
            low = mid + 1;
        }

        /* Too high. */
        else if (cmp > 0.0) {
            high = mid - 1;
        }

        /* Key found. */
        else {
            return mid;
        }
    }

    /* Key not found. */
    return ~low;
}

function shuffle(array) {
    var rand, index = -1,
        length = array.length,
        result = Array(length);
    while (++index < length) {
        rand = Math.floor(Math.random() * (index + 1));
        result[index] = result[rand];
        result[rand] = array[index];
    }
    return result;
}

function search1(response) {
    var list = [];


    [].concat(response.payload.SEARCH || []).forEach(function (result) {
        [].concat(result.attributes || []).forEach(function (nr) {
            nr = Number(nr && nr.value || nr || 0) || 0;
            if (list.indexOf(nr) < 0) {
                list.push(nr);
            }
        });
    });

    list.sort(function (a, b) {
        return a - b;
    });
    return list;
}

function search2(response) {
    var cmp = function (a, b) {
        return a - b;
    };
    var list = [];

    [].concat(response.payload.SEARCH || []).forEach(function (result) {
        [].concat(result.attributes || []).forEach(function (nr) {
            nr = Number(nr && nr.value || nr || 0) || 0;
            var idx = binSearch(list, nr, cmp);
            if (idx < 0) {
                list.splice(-idx - 1, 0, nr);
            }
        });
    });

    return list;
}

function testSingle(count, func) {
    var arr = [];
    for (var i = 0; i < count; i++) {
        arr.push(i);
    }
    arr = shuffle(arr);

    var response = {
        payload: {
            SEARCH: [{
                attributes: arr.slice(0, arr.length / 4)
            }, {
                attributes: arr.slice(arr.length / 4, arr.length / 2)
            }, {
                attributes: arr.slice(arr.length / 2, arr.length / 2 + arr.length / 4)
            }, {
                attributes: arr.slice(arr.length / 2 + arr.length / 4, arr.length)
            }]
        }
    };

    var s = Date.now();
    func(response);
    var e = Date.now();
    return e - s;
}

function test(steps, func1, func2) {
    for (var i = 0; i < steps.length; i++) {
        console.log('%s,%s,%s', steps[i], testSingle(steps[i], func1), testSingle(steps[i], func2));
    }
}

var steps = [120, 1200, 12000, 24000, 48000, 96000, 120000, 240000, 320000, 480000, 600000, 720000, 840000, 960000, 1080000, 1200000];
console.log('ITEMS,SORT,BINS');
test(steps, search1, search2);