profile

Hi! I'm Adam Gordon Bell

Sleep Sort

Published 9 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 June 4th Hey, It's June now, and I have a new episode out here: Hedy https://corecursive.com/hedy-with-felienne-hermans/ I've been telling friends and colleagues about this episode for several weeks. Whenever someone asks me how the podcast is going, I jump into it: Ok, Imagine this: A burned-out academic seeks renewal by teaching underprivileged 12-year-olds to program. In doing so, she risks her career and builds a programming language that spreads around the world and...

9 days ago • 1 min read

Adam Gordon Bell May 3rd One Hundred Episodes Hello, CoRecursive newsletter subscriber, It’s May now, and I have a new episode out. But it’s just not just any episode 100, and it’s something special. : 100! https://corecursive.com/coding-machines-with-don-and-krystal/ It's a story about debugging code, and I don't want to spoil it, but it blew my mind. It's about questioning the trust we put in our tools when building software. Also, Don and Krystal are back and sharing reflections on the...

about 1 month ago • 1 min read

Adam Gordon Bell April 2nd Skateboarding Meets Software Welcome to April and a new CoRecursive episode: Code, Kickflips and Crunch Time: Mick West's Neversoft Journey How do you build one of the most successful video games? The one that tops the charts, leads to a franchise and becomes a cultural phenomenon? Today, Mick West shares the story behind his incredible career and behind creating The Tony Hawk Pro Skater game. Find it in your podcast player or on the website. Repetition And Fluency...

2 months ago • 1 min read
Share this post