Sleep Sort


Adam Gordon Bell

Oct 2nd

Sleep Sort

Hello CoRecursive newsletter subscriber,

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

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.

!/bin/bash
function f() {
sleep “$1” echo “$1”
}
while [ -n “$1” ]
do
f “$1” &
shift
done
wait

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

Hi! I'm Adam Gordon Bell

Get a monthly update on my podcast, writing and whatever else I'm up to.

Read more from Hi! I'm Adam Gordon Bell

Adam Gordon Bell May 2nd Hey! Do you recognize this man? Well, he has some things to teach us about learning in the latest episode: https://corecursive.com/the-power-of-context/ Todays' podcast episode is about how to learn hard things. Guest Steve Krouse ( not pictured ) was a struggling student when he joined an after school program based around programming and some revolutionary teaching methods. That after school program changed his life in pretty profound ways. Today's episode is all...

Adam Gordon Bell April 2nd Hey! I have a new podcast episode out about this graph: I know that doesn't sound exciting, but it actually is! https://corecursive.com/briffa-sep98-e/ That is a famous climate change graph that caused a lot of controversy, with newspapers and news shows accusing scientists of fraud and deception. While scientists claimed they were victims of a targeted attack. I got a little obsessed with what actually happened. It happened 15 years ago, but the code is still out...

Adam Gordon Bell Oct 2nd Hey! I have a new podcast episode is out: https://corecursive.com/one-million-checkboxes-with-nolen-royalty/ It's at the intersection of coding, game building, art and online trolls. That is to say it's a super fun episode about building something and having it become really really huge and all the unexpected things that follow. But it's also about how the internet used to be more fun, and how Nolen Royalty is trying to bring us back to the era of Boaty McBoatface I...