## The Tick Sort

*Posted by Software Engineering on*in

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:

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: