Sleep Sort

June 15, 2011 5:20 PM

4chan's texboard /prog/ invents a novel new sorting algorithm(no images, but NSFW with a few reprehensible bits thrown in) called sleep sort and translates it into most most modern programming languages. Hacker News provides analysis and finds itself impressed.
posted by Ad hominem (51 comments total)

O(ℕ)
posted by Blazecock Pileon at 5:26 PM on June 15, 2011 [1 favorite]

This is flavors of the CUDA radix sort implemented in the CUDPP library.

Clever non the less.
posted by The Power Nap at 5:26 PM on June 15, 2011

hacker news link goes to 4chan
posted by unSane at 5:33 PM on June 15, 2011

O(exp(N)), actually. If the input is 9999, it takes 4 digits of input (N=4) but O(10^4) time to run.
posted by jewzilla at 5:33 PM on June 15, 2011 [1 favorite]

Anyone care to tell the rest of the world what this means?

(I generally consider myself pretty geeky, but I'm lost.)
posted by toekneebullard at 5:37 PM on June 15, 2011 [3 favorites]

Is this something you'd have to be a programmer to understand?
posted by jessssse at 5:37 PM on June 15, 2011

it actually delegates the actual sorting to the thread scheduling algorithm, so it can't do any batter than that and it does a lot worse since it adds a bunch of constant overhead.

I thought it was funny, but it's not an algorithm. it's a programmer joke.
posted by GuyZero at 5:39 PM on June 15, 2011 [3 favorites]

Clever? Yes. Silly? Yes. Useful? Not really.

I wouldn't really call it an algorithm so much as a trick, which is that you offload the sorting action onto the kernel's thread scheduler. Each integer gets converted into a "time to wake up this thread" value which the kernel then sorts (usually via an insertion sort).
posted by RobotVoodooPower at 5:39 PM on June 15, 2011 [1 favorite]

Anyone care to tell the rest of the world what this means?

As mentioned, it's a sorting algorithm (i.e. a method of sorting things, in this case numbers, specifically positive integers in most implementations of the method). It works like this:

Say you have a list of numbers (e.g. 5, 3, 1, 2, 4) and you want to sort them in ascending order. Take each number, tell the computer to wait that many seconds and then print the number. So the computer will wait 5 seconds and print a 5, 3 seconds and print a 3, and so forth. The clever bit is that the computer can wait on all of those at the same time. So it will print the 1 after 1 second, the 2 after 2 seconds, and so forth.

The obvious downside is that you have to wait an arbitrarily long time for the method to finish, depending on how large the numbers you are sorting are. Also, the whole thing is actually just piggy-backing on the way the computer sorts the list of things it's waiting for.
posted by jedicus at 5:42 PM on June 15, 2011 [19 favorites]

For those who don't grok programming: for each of the numbers in the list you give it, start a process that waits that number of seconds then prints the number. Smaller numbers will get printed first, larger numbers will get printed last. Your list is now sorted!

Except, due to lots of fiddly details, not necessarily and lots of work is done under the hood for you by the operating system.
posted by lantius at 5:42 PM on June 15, 2011

I usually just sort my novels alphabetically.
posted by cmoj at 5:42 PM on June 15, 2011 [4 favorites]

Anyone care to tell the rest of the world what this means?

(I generally consider myself pretty geeky, but I'm lost.)

It's sorting a list of numbers in the following way (using the example numbers 10, 55, 1, 12):

1. Hey Fred, wait ten seconds and then say "ten".

2. Hey Joe, wait 55 seconds and then say "fifty-five".

3. Hey Maureen, wait a second and then say "one".

4. Hey Janine, wait twelve seconds and then say "twelve".

Assuming that you said all of those things simultaneously or close to it, and that those four people followed your instructions, what would be said (after 55 seconds total) would be:

"One."

"Ten."

"Twelve."

"Fifty-five."

That is, the list has been sorted in increasing order.
posted by Flunkie at 5:43 PM on June 15, 2011 [12 favorites]

...called sleep sort and translates it into most most modern programming languages.

But can it be translated into Hungarian folk dance?
posted by 445supermag at 5:44 PM on June 15, 2011 [2 favorites]

It's a programmer's little poem, and like most poems, "lots of work is done under the hood."
posted by StickyCarpet at 5:45 PM on June 15, 2011 [4 favorites]

When I need to sort numbers I do it in O(1) time.

First, I represent each number with a piece of spaghetti whose length is proportional to the value. Than I take all the pieces of spaghetti in a bundle and I gently put one end of the bundle on a table.

Voila. Sorted. In one step.
posted by GuyZero at 5:46 PM on June 15, 2011

My favorite linear time sort is spaghetti sort.
posted by jewzilla at 5:47 PM on June 15, 2011 [2 favorites]

Damn, GuyZero beat me to it :)
posted by jewzilla at 5:47 PM on June 15, 2011

(but it's still O(N) because you have to pick off N pieces of spaghetti; otherwise you're just getting the max. Also, it takes O(N) time to prepare the spaghetti.)
posted by jewzilla at 5:48 PM on June 15, 2011

You can eat the spaghetti afterward, unlike shell sort.
posted by twoleftfeet at 5:50 PM on June 15, 2011 [3 favorites]

Meh. Even as a joke, this is not that nifty.
posted by ryanrs at 5:50 PM on June 15, 2011

This looks like a weird time-based version of a Pigeonhole Sort. You could probably improve speed by scanning the list for largest and smallest values, then going back over it and re-mapping it through a logarithmic-like function.
posted by adipocere at 5:52 PM on June 15, 2011 [3 favorites]

Hey, it's better than Bogosort.
posted by Ad hominem at 5:55 PM on June 15, 2011

Yeah, bascially, waitable timer events - you use the scheduler to order the sort for you. It's an interesting way to do things, but pretty lousy in terms of performance.
I still find it funny that new interns are amazed that you can get sorted results from using typical C++ "map" implimentations.
posted by Old'n'Busted at 5:56 PM on June 15, 2011

This is hilarious.
posted by Threeway Handshake at 6:01 PM on June 15, 2011 [1 favorite]

The obvious downside is that you have to wait an arbitrarily long time for the method to finish, depending on how large the numbers you are sorting are. Also, the whole thing is actually just piggy-backing on the way the computer sorts the list of things it's waiting for.

The first can be overcome by using a smarter way to decide how long to sleep for any given thread, and the second can be overcome by using different hardware, for example:

To sort N numbers, have N + 2 actual separate processors. The first processor is connected to each of the next N processors via two wires:

(1) Here's the number you're responsible for;

(2) GO!

The last processor is connected to each of the previous N processors with one wire:

(1) Here's the number I was responsible for.

The "GO!" wires are all set up to be fired simultaneously - i.e. it's really one wire coming out of the first processor, which branches into N parallel wires of equal length and resistance.
posted by Flunkie at 6:15 PM on June 15, 2011

Yep, I invite you all to consider, predictability, CPU load and parallelization.
posted by Ad hominem at 6:25 PM on June 15, 2011

The "GO!" wires are all set up to be fired simultaneously - i.e. it's really one wire coming out of the first processor, which branches into N parallel wires of equal length and resistance.

Leading you to an insurmountable race condition.
posted by Threeway Handshake at 6:45 PM on June 15, 2011

I sort M&Ms, Skittles, and Smarties by color, count the number of candies per color, eat firstly the candies which are in excess of the lowest such number (thus evening the number of candies per group), then, going in order of color placement on the visible spectrum, sequentially eat candies from each group such that I ingest each color with equal frequency until the candy is finished.

That is my colored candy eating algorithm. It is not very efficient.
posted by dephlogisticated at 6:46 PM on June 15, 2011 [14 favorites]

O(M&M)
posted by twoleftfeet at 6:55 PM on June 15, 2011 [8 favorites]

OK, cosmic weirdness time.

I found myself thinking about something I hadn't thought about in probably a decade or more - the sort pump, another sorting algorithm that allegedly sorts in O(n). I learned about it at the University of Kent (where I believe it was invented) and it was presented as a somewhat non-serious example in our occam programming class.

Here it is in Haskell.

Finding this post here tonight was enough to give me chills up the spine ...
posted by kcds at 7:04 PM on June 15, 2011

One of the most beautiful and most disturbing things about the internet is the constant revelations it provides of one fact: no matter how weird I am in so many ways, there's always someone else out there who's even a little weirder in just the same way. Thank you, dephlogisticated. Now, the next time I eat my sorted N_flavors * N_remaining_per_flavor Skittles in evenly distributed order, I can reassure myself that at least I'm not doing that with M&M colors! Now that would just be crazy.
posted by roystgnr at 7:38 PM on June 15, 2011 [1 favorite]

The "GO!" wires are all set up to be fired simultaneously - i.e. it's really one wire coming out of the first processor, which branches into N parallel wires of equal length and resistance.

Leading you to an insurmountable race condition.

In what way?

If the N middle processors receive "GO!" simultaneously, within tolerable bounds, and they're able to handle a single timer to a tolerable precision, and deliver their output to the N+2 processor (the output processor) within a tolerable precision of a known amount of time from the time that their timers expire, then that output processor will receive their outputs in the proper order.

Saying that it's an "insurmountable race condition" seems, to me, to be assuming some bound on the precision of the hypothetical hardware that simply cannot be assumed.
posted by Flunkie at 7:39 PM on June 15, 2011

Could be optimized a little:

sleep "$1d"

posted by swift at 7:47 PM on June 15, 2011

And behold! Moses sorted the Red Sea.
posted by localhuman at 7:48 PM on June 15, 2011

That's not a new sorting algorithm. It's effectively just a subroutine call to whatever sort algorithm is used by the scheduler. Every time I invoke the sort command, or call a library routine, I'm not inventing a new O(1) sort algorithm.
posted by axiom at 7:48 PM on June 15, 2011 [1 favorite]

axiom, again, your point that it implicitly uses the sort algorithm of the scheduler is assuming that it's being done naively on a single processor.
posted by Flunkie at 7:49 PM on June 15, 2011

Sorry Flunkie, should've made it clear -- I was talking about the OP.
posted by axiom at 8:01 PM on June 15, 2011

Yes it is hilarious, but it's basically just pigeonhole sort with the dimension of time replacing the pigeonhole array.
posted by aeschenkarnos at 8:44 PM on June 15, 2011

(as adipocere noted)
posted by aeschenkarnos at 8:46 PM on June 15, 2011

I prefer: if you give an infinite number of monkeys a deck of cards, each thrown for 52 card pick up...
posted by BigHeartedGuy at 9:18 PM on June 15, 2011

Ha! I remember the first time I thought of the pigeonhole sort. I figured I was a genius.

At least I didn't tell anyone about what I had "invented" before I found out how late to the party I was.
posted by Bonzai at 9:31 PM on June 15, 2011

Since no-one else has pointed it out, I'll copy the Perl6 implementation from the 4chan post:

@foo = @foo>>.&sleep;

I don't understand it, but it both thrills me and scares me at the same time. (And apparently as of now it's only been specified, not implemnted.)
posted by benito.strauss at 9:56 PM on June 15, 2011 [1 favorite]

I think that sebastianbailard accidentally posted the APL implementation to another thread.
posted by Flunkie at 10:10 PM on June 15, 2011 [3 favorites]

Anyone care to tell the rest of the world what this means?

One thing that might be missing from some of the explanations is why sorting algorithms are a big deal. The reason is that the most crucial factor to consider for how efficiently any algorithm performs, in either memory or time, is scalability. In other words, how much impact on the performance is there when you double (or triple, or whatever) the number of items to sort? There is a formal metric that programmers use to measure the efficiency of an algorithm in terms of scalability, and it's generally called "Big O Notation."

This one is unique because it scales extremely well ("O(n)" in Big O notation), but it is also unique in how it is limited. Generally, the performance of a sorting algorithm has no relationship to the actual values being sorted, but in this case, it is heavily dependent. I'd say it could be used to sort certain kinds of data exceptionally well (e.g. integers spread over a small range without too many repetitions), while it should not even be considered for certain others (e.g. floating point numbers). The limitations on range and repetition effectively kill most of its scalability advantages.
posted by Edgewise at 10:59 PM on June 15, 2011

Oh, something I forgot to mention: There are two reasons that sorting algorithms, in particular, are a big deal. First, it is a very common kind of generic task that must often be performed in software. Second, for large data sets, sorting can take a long time. Thus, an efficient sorting algorithm can have a big impact on software performance for many applications. As such, abstract sorting algorithms have been much investigated and researched, and new ideas don't show up every day. Sorting is one of the first meaty topics that is a part of any software engineering curriculum.

That was probably more than you needed to know...
posted by Edgewise at 11:09 PM on June 15, 2011

Non-programmer speaking: So this only works with lists of numbers? What if I want to alphabetize? Or do you just assign each letter a number or use the hex or something?
posted by maryr at 7:56 AM on June 16, 2011

This is really silly.
posted by ph00dz at 8:02 AM on June 16, 2011

Non-programmer speaking: So this only works with lists of numbers? What if I want to alphabetize? Or do you just assign each letter a number or use the hex or something?

Strings (text data) are numbers, almost always according to a standard scheme like ASCII. If ASCII (and more modern schemes based off it) didn't represent letters in alphabetical order, sorting would get more complicated, and in fact it does get more complicated if you want to properly alphabetize non-English text -- or even English text, since English has a lot of foreign loanwords that use accents and diaereses and the like.
posted by neckro23 at 8:10 AM on June 16, 2011

That is my colored candy eating algorithm. It is not very efficient.

I do the same thing. I had no idea there was anyone else.
posted by Mars Saxman at 11:18 AM on June 16, 2011

Leading you to an insurmountable race condition.

It's okay if all of the scheduling happens before the first timer is triggered.

I think someone else pointed it out, but this is just insertion sort, with the insertions being outsourced to the scheduler.
posted by qxntpqbbbqxl at 7:07 PM on June 18, 2011

Bonzai At least I didn't tell anyone about what I had "invented" before I found out how late to the party I was.

You should be proud of yourself for independently inventing a useful and interesting algorithm. It's unprovable that you did it independently, so the circumstances under which you can mention it to others are limited, but in your own head you can still give yourself credit. Well done. Also, if you came to the conclusion through a different path of reasoning, that can still be useful to share.

"Firstness" is drastically overrated, primarily due to the cultural influence of patent and copyright law.
posted by aeschenkarnos at 5:34 AM on June 19, 2011