profile

Hi! I'm Adam Gordon Bell

Sleep Sort

Published 5 months ago • 2 min read

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 Feb 2nd Beautiful Code Welcome to February and a new CoRecursive episode: Beautiful Code - Inside Greg Wilson's Vision for Software Design Greg Wilson has been on a decades-long quest to transform how we teach and talk about software design. From getting rejections for using the term "beautiful code," to empowering scientists through workshops on Python and Unix, Greg has pushed to bridge the gap between theory and practice. In this episode, Greg shares his failures and...

28 days ago • 3 min read

Adam Gordon Bell Jan 2nd Brain Injury Sparks Python Mastery Welcome to 2024 and a new CoRecursive episode: Code As A Lifeline What if your dreams were suddenly ripped away? What if your talents vanished, your passions erased? That’s what happened to Jason McDonald when a traumatic brain injury at 16 ravaged his planned destiny of becoming a doctor. Jason painfully rebuilt his identity from scratch - relearning to read, write, and even speak. A serendipitous discovery of coding ignited a new...

about 2 months ago • 3 min read

Adam Gordon Bell Dec 4th Echoes of Creation: Decoding Vue's Genesis and the FTX Saga Hey, It's December now, and I have a new podcast episode out here: From 486 to Vue.js - Evan You's Full-Time Gamble on Open Source It's the unlikely origin story behind Vue.js and how Evan You's frustration with Angular sparked a side project that snowballed into one of today's most popular JavaScript frameworks. Two of the big focuses are: 1) What happens when your hobby project takes on a life of its own?...

3 months ago • 3 min read
Share this post