Sleep Sort

Hello CoRecursive newsletter subscriber,

It’s October now, and I have a new episode out here:

• ​Sloot Digital Coding System​

Jan Sloot claimed to have invented revolutionary data compression that could fit a full movie into a tiny smart card chip. Top executives and investors witnessed his demos and became true believers, ready to bankroll this company into the stratosphere.

But was it all an elaborate illusion? Check out the episode and let me know your thoughts.

Pi Compression and Sleep Sort

This month’s episode mentions my idea for a compression algorithm that wouldn’t work. My idea – it turns out - wasn’t original ( a joke implementation exists ).

Here is another magical seeming solution: Sleep sort.

What this is doing, if you don’t love bash like I do, is just starting a new process for each element and having it sleep until it’s time to print its number.

The downside here is clearly that sorting a list will take as many seconds as the total number of elements in the list. But the potential upside is how little absolute work needs to be done.

To sort a list like [5,3,6,3,6,3,1,4,7] with a standard sort method like merge sort would take 21 comparisons ( I counted), but sleep sort never compares anything and only needs to call sleep nine times to sort this list.

How can this be?

Sleep sort was not the output of Computer Science research, like QuickSort or MergeSort, but instead published on 4Chan.

​

Sleep sort is different from Pi Compression in that it does work. If your list is short enough, and you aren’t afraid to wait max N seconds, sleep sort will work.

The trick is its supposed efficiency. With our [5,3,6,3,6,3,1,4,7] example, sleep sort only performs nine sleeps, but how are those sleeps implemented? Well, it depends on the operating system, but it’s certainly not free.

If we pretend the operating system scheduler is a priority queue, then removals are 0(n log n), meaning it would take about 28 comparisons for our list of 9. This is in the range of what merge sort would do.

But in practice, things are far worse than this. The Linux scheduler is quite complex, concerning itself with process priority and fairness. Because of this, it could take more like 81 comparisons ( n^2), and that doesn’t count the overhead of context switching and process creation.

So, sleepsort is not efficient. It just hides the overhead in a place we aren’t used to looking. But it’s an excellent curiosity because its seemingly absurd assertion gives a lens for digging into how things on computers work. Thank you, 4chan.

Take a look at pingfs for another example.

Thanks Again

This month’s podcast episode is an exploration of a similar mysterious tech claim, but it’s combined with a start-up story and a mysterious death. I hope you like it, and I’d love to hear your thoughts.
Thanks,

Adam

​@adamgordonbell​

​Unsubscribe · Preferences​