On: Sleep sort (2011)

[avodonosov]

javascript version (faster):

    var input = [5, 3, 6, 3, 6, 3, 1, 4, 7];

    var timeAxis = [];
    // Put every element to the corresponding time point.
    // Time point would hold an array, as we can have
    // equal elements.
    for (var i = 0; i < input.length; i++) {
        elem = input[i];
        timeAxis[elem] = [elem].concat(timeAxis[elem] || []);
    }

    // skip all empty (UNDEFINED) time points
    // and contact all the arrays:
    var sorted = timeAxis.reduce(function (accum, cur) {
                                     return cur ? accum.concat(cur) : accum},
                                []);
    console.log(sorted)

[avodonosov → avodonosov]

The speedup is from usage of _virtual time_, which we don't need to wait for.