Sleep sort (2011)

http://dis.4chan.org/read/prog/1295544154/

by olalonde • 12 years ago

326 68 12 years ago

dis.4chan.org

codezero3• 12 years ago

This is my new favorite after bogosort.

I'm sad nobody has implemented my idea, rock, paper, scissors sort.

mc_hammer• 12 years ago

lmao i actually looked that up, it even has a wikipedia entry. what a good read.

sebastialonso• 12 years ago

Care to share the look link? Couldn't find it.

maaaats• 12 years ago

My favorite is spaghetti sort. Make one spaghetti straw per item that is as long as the value of the item. Then take all spaghettis in your hand and put them against a flat surface. Remove the longest one and keep doing that. :)

kevinwang• 12 years ago

And what, exactly, is rock paper scissors sort?

codezero3• 12 years ago

The comparison function is a game of Rock Paper Scissors with the winner being given the 'greater than' position. Games proceed until all items are in sorted order :)

antics11• 12 years ago

Just to be 100% clear, in case anyone who is new to the field stumbles on this thread, this is NOT breaking math or anything. This is a fun, but totally normal result.

First of all, there are quite a few linear time sorting algorithms. Radix, pigeonhole, and counting sort are all linear time sorting algorithms. The popular result that any comparison-based sorting algorithm works in O(n log n) applies _specifically_ to comparison-based sorting algorithms, and not those like the above. So, even if you ignore the underlying mechanics of the OS scheduler and assume sleep works "perfectly", the result would not that unusual.

Second off, in the comments there appears to be considerable time worrying about the technicalities of the scheduler, the nondeterministic nature of sleep, and so on, and whether this really implies linear time bound. IMHO these are not worth worrying about because we already have linear time sorting algorithms. It's fine to assume the scheduler adds no significant asymptotic cost here, even if we know differently.

Third off, remember that all of these sorting bounds assume machines of the Von Neumann architecture. In particular, this model assumes constant time memory and constant time comparison operations. In cases where you're comparing really big numbers, these bounds get worse. This is easy to forget, but worth remembering just since we're on the subject anyway.

wcrichton2• 12 years ago

This is not "linear time" in any decent sense--we shouldn't conflate the number of elements with the size of the elements (in this case, O(max element) is actually exponential in the input size!).

duaneb• 12 years ago

Yea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.

asdfaoeu• 12 years ago

the max size of the elements is usually constant when comparing sorting algorithms. The complexity of this depends on the algorithm of the scheduler. With the right scheduler this could be O(nlog n).

antics11• 12 years ago

This isn't really right. If the numbers can be arbitrary in size, then you can't compare them in constant time, which means that comparison-based sorts are quadratic.

This is directly related to my third point. Traditional analysis of sorting algorithms assumes the Von Neumann architecture, and in particular, it assumes constant-time comparisons.

SilasX• 12 years ago

I thought that too, but couldn't you make element size irrelevant by renormalizing the list? One pass to find the max, one pass to divide everything by it.

gpfault• 12 years ago

It's more like O(max(input)), not O(n) (see the first response)

davrosthedalek• 12 years ago

You can always scan through the array, rescale everything by 1/max(input). Then the sleep part is O(1) and the scan part is O(n) -> O(n) total.

fennecfoxen• 12 years ago

Well. Let's distinguish between computational complexity and wall-clock time. The code you write yourself here performs operations with O(n) asymptotic complexity where n is the number of elements, but the system scheduler may be able to find additional work to do while the algorithm is waiting to resume, or even put the CPU into a lower-energy state.

Of course, making lots of system calls to create processes and store them in your operating system's process table almost certainly invokes operations with greater than O(n) asymptotic complexity, but this complexity is still unrelated to max(input).

sorbits• 12 years ago

there appears to be considerable time worrying about the technicalities of the scheduler […] whether this really implies linear time bound. IMHO these are not worth worrying about

But it is not linear time, we shouldn’t let the existence of other algorithms make us confused about proper analysis of this one.

The call to `sleep(n)` is not a trivial operation, it inserts our task into a priority queue, so we are piggybacking on the OS’ support for sorting tasks based on when they need to be woken up, and thus hide the actual complexity behind the call to `sleep` (which we call `n` times, so if it’s `lg(n)` then the time complexity of the entire algorithm is `O(n lg n)`).

bane2• 12 years ago

It's also a good example of why O() isn't the entire story when it comes to how long an algorithm takes to run.

detrino2• 12 years ago

This is not a linear time sort. This is just sorting using a priority queue (aka heap sort) with arbitrary pauses thrown in. Here is a simplified model of what is going on (http://ideone.com/azLsTc). Note that line 31 (the sleep until) is totally irrelevant to the sorting.

antics11• 12 years ago

No, sorry, that's not correct, it's not a decided issue whether it's linear time or not. It depends on what assumptions we _decide_ to make about the scheduler and the OS, what the API for sleep is, and so on.

One reasonable assumption is of course to assume that sleep works as it does on virtually all modern OSs, in which case, you're correct, but that is certainly not the only way it can be. You could easily imagine a specialized SortOS that executes one thread on one process and outputs messages at a specifically scheduled time after a program begins executing, in which case the result would be radix sort with extraneous waiting, rather than priority heap sort with extraneous waiting.

danso• 12 years ago

Sadly, the somewhat lengthy Wikipedia entry for Sleep sort was deleted. Here's archive.org's version:

https://web.archive.org/web/20110622073615/http://en.wikiped...

Reading through Wikipedia's existing pages for other esoteric sorts makes me laugh as I did when reading Hitchhiker's Guide to the Galaxy's various entries for scientific theories (e.g. Bistromathics)...There's Bogosort, Stooge sort, American flag sort, and my favorite, "Gnome sort", named thusly because "that is 'how a gnome sorts a line of flower pots'" http://en.wikipedia.org/wiki/Gnome_sort

Al-Khwarizmi• 12 years ago

Gnome sort used in a practical application (for natural language parsing): http://stp.lingfil.uu.se/~nivre/docs/gotal.pdf

seabee• 12 years ago

Unlike most esoteric algorithms, American flag sort is actually pretty useful in its niche of string sorting.

drcomputer• 12 years ago

But why. I would think the gnome is the perfect size to pick up exactly one flower pot (the next smallest) and would also be able to recall a dividing line (because the gnome is tiny and prefers traveling less).

chriswarbo2• 12 years ago

I like the comparison between the incredibly inefficient Bogosort:

    1) Shuffle the list.
    2) If it's sorted, halt.
    3) If it's not sorted, go to step 1.

and the incredibly efficient Quantum Bogosort:

    1) Shuffle the list.
    2) If it's sorted, halt.
    3) If it's not sorted, destroy the Universe.

According to the Many Worlds interpretation, step (1) creates multiple Universes, each with a different ordering of the list. Step (3) ensures that, by the anthropic principle, we must be in a Universe where the list was sorted correctly (otherwise we wouldn't be around to observe anything).

TheSoftwareGuy• 12 years ago

how does it destroy the universe though? I am really not very familiar with things in the quantum world and that kind of stuff.

bane2• 12 years ago

Of course, why wouldn't WP delete it? <sarcasm>

I just found out that the WP page for the hornet archive, one of the most important focal points of the international demoscene for a decade, was deleted because it was't "notable".

So frustrating.

angersock2• 12 years ago

Shame, isn't it?

SwellJoe• 12 years ago

Previous discussion: https://news.ycombinator.com/item?id=2657277

Pretty sure it's been posted a couple other times, but I'm on a tablet at the moment.

shultays• 12 years ago

Didn't saw this post before

I heartily disagree with all the attempts to downplay the brilliance of the sleep sort algorithm. Many of you have missed the important point that while traditional sorting algorithms can only utilize one core, sleep sort has the capacity to use the full power of a massively parallel execution environment.

Given that you need nearly no computing in each of the threads, you can implement them using low-power CPUs, so this is in fact a GREEN COMPUTING algorithm.

Oh, and did I mention that the algorithm can also run inside a cloud...?

Sure, you're a genius!

majke• 12 years ago

With fluxcapacitor it will run in fraction of a second!

https://github.com/majek/fluxcapacitor#basic-examples

$ ./fluxcapacitor examples/sleep_sort.sh 1 4 20 3 55

ambrop72• 12 years ago

I remember a few years ago, I hacked up the Wine source code so some skiing game would run at half speed. It totally worked :) It was even simpler than fluxcapacitor since you don't need to hook anything but just change the implementation of some time related functions.

perlgeek• 12 years ago

Recently I wrote about sleepsort for the Perl 6 advent calendar, mostly as a fun topic to talk about threads, promises etc.

http://perl6advent.wordpress.com/2014/12/23/webscale-sorting...

ambrop72• 12 years ago

One should know that it is the timer scheduler of the kernel which ends up doing the sorting. With Linux, this is probably a red-black tree[1], so performance of sleep sort (when it works) is O(n *log(n)).

[1] https://www.kernel.org/doc/Documentation/timers/hrtimers.txt

logicallee• 12 years ago

if you'd like to trade space for time, here is another sort with no comparisons: http://codepad.org/0k2Ou2Db

vlad003• 12 years ago

I don't know Perl, so I rewrote it in Python in an attempt to understand what's going on: [link redacted]

I'm not storing key,value pairs for elements that don't exist (not sure what the Perl code's doing), so it shouldn't be too bad in terms of space used.

woadwarrior01• 12 years ago

I'm not entirely sure about this, but it looks more like Counting sort [1], than Pigeonhole sort.

[1] https://en.wikipedia.org/wiki/Counting_sort

xianshou• 12 years ago

Radix sort, with time as the buckets...stylish.

avodonosov2• 12 years ago

javascript version (faster):

    var input = [5, 3, 6, 3, 6, 3, 1, 4, 7];

    var timeAxis = [];
    // Put every element to the corresponding time point.
    // Time point would hold an array, as we can have
    // equal elements.
    for (var i = 0; i < input.length; i++) {
        elem = input[i];
        timeAxis[elem] = [elem].concat(timeAxis[elem] || []);
    }

    // skip all empty (UNDEFINED) time points
    // and contact all the arrays:
    var sorted = timeAxis.reduce(function (accum, cur) {
                                     return cur ? accum.concat(cur) : accum},
                                []);
    console.log(sorted)

avodonosov2• 12 years ago

The speedup is from usage of _virtual time_, which we don't need to wait for.

veesahni• 12 years ago

(impure) ruby implementation:

ruby -e '[3,1,2].each{|n| system("sleep #{n} && echo #{n} &")}'

Nimi• 12 years ago

Pardon the shameless plug, but I've recently used a similarly unorthodox approach for replacing the heap inside Dijkstra's algorithm, and got a speedup - I use an array indexed by the vertices' current distances, and scan it from start to finish.

A paper is currently making the rounds, would love to hear feedback:

https://www.dropbox.com/s/zy1gx1azfvvqm6i/NetSciComm%20versi...

bluecalm• 12 years ago

C implementation for Windows:

  #include <stdio.h>
  #include <windows.h>
  #include <process.h>
  
  void sleep_on_it(void* param)
  {
      int n = *(int*)param;
      Sleep(n);
      printf("%d ", n);
  }
  
  int main(int argc, char **argv)
  {
      int ar[argc];
      HANDLE threads[argc-1];
      for (int i = 1; i < argc; i++){
          ar[i] = atoi(argv[i]);
          threads[i-1] = (HANDLE)_beginthread(&sleep_on_it, 0,  &(ar[i]));
      }
      WaitForMultipleObjects(argc-1, threads, TRUE, INFINITE);
  }

Compile with gcc -std=c99 (because of VLA's it won't work in Visual Studio).

Example:

D:>sleepsort 1000 9 2 150 1 7 17 624

1 2 7 9 17 150 624 1000

taternuts• 12 years ago

This guy makes the rounds every once in awhile it seems. Here's a /r/dailyprogrammer thread with solutions in various languages: http://www.reddit.com/r/dailyprogrammer/comments/yqydh/82420...

angersock2• 12 years ago

For the record, in that thread, there are implementations in Bash, Erlang, Haskell (I think), Perl, C, and Racket. It also is interspersed with entertaining banter and unentertaining racism. So, basically, a more caustic more technical less orderly version of HN. Think about that.

There's a reason 4chan should be considered a national...maybe not treasure, but it's pretty awesome.

matheusbn• 12 years ago

Do you mind if I submit a javascript version!?

http://js.do/code/48519

http://js.do/code/48526 (Optimized milliseconds). :)

Sleep sort (2011)

Related Stories