Steve the Dev

While browsing Reddit — as one does — I stumbled across a horrible, no-good, very bad sorting algorithm, entitled the Variety Sort. So, naturally, I used this obvious "look at this clearly absurd idea" kind of joke into an actual algorithm... for science, of course. After admiring my handy-work, I started thinking about ways I could make a similarly terrible sorting algorithm — and that's where I got the idea for what I'm going to call the Tick Sort.

How does it work?

The Tick Sort works by abusing the Event Loop — the language feature that makes JavaScript asynchronous. Consider this code:

console.log('Start');
setTimeout(function() { console.log('Middle'); }, 0 /* milliseconds */);
console.log('End');

What order do these execute? In this example, setTimeout pushes the 'Middle' onto the Event Queue, and moves on to the'End'. You can check this yourself below:

Click Me

Node.js takes this idea a little bit further, and allows users to insert functions at the end of the current "tick". We can use this function to ensure that our sort algorithm finishes before the next tick of the Event Loop. Unfortunately (or fortunately, depending on your point of view) this makes the Tick Sort an asynchronous sorting algorithm.

Let's Build It!

async function tickSort(array) {
    let smallest = Infinity;
    for (let i = 0; i < array.length; ++i) {
        if (smallest > array[i]) {
            smallest = array[i];
        }
    }

    const values = array.splice(0, array.length);
    await Promise.all(values.map((value) => new Promise((resolve) => {
        return tickSort.schedule(resolve, array, value, value - smallest);
    })));

    return array;
}

tickSort.schedule = function schedule(resolve, array, value, wait) {
    if (wait > 0) {
        return process.nextTick(() => schedule(resolve, array, value, --wait));
    }
    array.push(value);
    return resolve();
};

Ok, so there's a lot going on here. I'll walk through it.

async function tickSort(array) { /* ... */ }

Since we are abusing the event loop to make this work, we have to make it an asynchronous function. If we don't, the line after the tickSort call will be working on an un-sorted array.

let smallest = Infinity;
for (let i = 0; i < array.length; ++i) {
    if (smallest > array[i]) {
        smallest = array[i];
    }
}

What happens if we have a value less than 0? We can't queue ticks to occur in the past, so we need to offset everything from the smallest value. This makes sure that the smallest value is determined, and offsets from that value to prevent negative values from being inserted.

const values = array.splice(0, array.length);

In this line, we are copying all of the values from array into values, and emptying array in preparation for us to move the sorted values back into it.

await Promise.all(values.map((value) => new Promise((resolve) => {
    return tickSort.schedule(resolve, array, value, value - smallest);
})));

This is where the magic starts. We convert the values array into a set of Promise objects, which must be fulfilled before the tickSort continues. As you can see, the fourth parameter is the difference between value and smallest.

tickSort.schedule = function schedule(resolve, array, value, wait) {
    if (wait > 0) {
        return process.nextTick(() => schedule(resolve, array, value, --wait));
    }
    array.push(value);
    return resolve();
};

And here's where the real magic happens. The schedule function recursively pushes itself to the back of the current tick's queue while decrementing from its fourth parameter with each run. Using process.nextTick ensures that this sort finishes before the next iteration of the event loop begins. Once wait hits zero, the value is pushed into the array and the recursive function exits.

But does it work?

Sure, depending on the values in the array.

• If a value is too large for JavaScript to decrement from; if Infinity or -Infinity shows up in a sorted array, since both of those would result in an infinite loop — Infinity minus 1 is still Infinity, after all.
• If some values can't be coerced to numbers, then they will be coerced to NaN and immediately pushed into the beginning of the array — letters, objects, for example.
• Non-integer decimal values (1.2, 1.452, 3.14159, etc.) can't be cleanly iterated toward. Therefore, 3.1 will be treated as 4, since 0.1 > 0.

Also, you should never use this algorithm in real code. It's cumbersome and has an unpredictable runtime. But it's still a pretty neat piece of trivia to geek over.

Feel free to give it a try, here: