Sleep sort (2011)
dis.4chan.org
dis.4chan.org
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.
E.g.
Intput, T: array of n elements, m: number of distinct elements.
for i in 1..m
for j in 1..n
if( T[j] == i ) print T[j];
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.
Go read the parent again. The author claims that sorting in this case takes time proportional to the size of largest element, and I'm saying, if it takes time proportional to the space consumption of in the largest element (presumably where the cost of the sort comes from), you can't define a computational model where comparison takes constant time -- it still has to read the digits, which we know takes linear time.
If your point is that you can define a model of computation with contradictions in it, then you should rethink whether what you are saying here is even relevant to the thread at all.
Short circuiting comparisons is still linear for integers of unbounded size. But besides that, it's incredibly common to assume that 64-bit primitives are done in constant time, because to the asymptotic analysis, what matters is that the integers are _bounded_ in size. As long as it's bounded, the asymptotic analysis here doesn't care -- you can pick any size you want, as long as it's bounded.
One thing to keep in mind here (which it seems you are maybe confused about) is that these bounds are _asymptotics_ of the input size generally, and have very little to say about any particular choice of input size. 64-bit, 32-bit, whatever, it doesn't matter, if the size of the operands is bounded, the they're the same thing to the asymptotic analysis. As long as they're bounded, you can say that the operations on those operands is proportional to a constant times the (bounded) size of the operands.
The consequence of this is that when you deal with operands of _unbounded_ size, all of this asymptotic analysis goes right out the window. You can't possibly have a meaningful comparison operator, for example, that operates in constant time on unbounded integers.
Short circuting cuts that to log(log(N)) on average and log(N) worst case.
It's actually generally faster to compare X bytes of Vary large numbers than X Bytes of long int's. Degenerate case being 2 numbers of x/2 bytes.
Anyway, the point is treating log(log(N)) as constant is generally reasonable especially when N is small.
We don't really deal with unbound integers worst case is something like 2^(2^1,000,000,000,000,000,000)) before we can't actually store them.
Even then log of log of N makes random numbers of that size practically constant time to compare. Put another way there is less than 1 in 2^64 you need to do more than 3 comparisons and less than one in 2^128 you need more than 4. One for length, one for the chunk which might be just one bit and one more for the next 64 bits. Sure that might happen, but reolistically random input is unlikely to need many comparisons.
Stings on the other hand are more of an issue.
Do you realize that the whole point of asymptotic analysis is that _we do not care_ what integers we "really" deal with? These bounds specifically deal with sorting arbitrary data of unbounded size, and _no other assumptions_.
Do you understand? No assumption that we can use parallelism. No games with integers you see in "real life". None of that is relevant. You can't play games with practicalities to get a better bound. This is the general bound, and if you fiddle with it to get something else, you are changing the scope of the question to be something else entirely.
If you want to have a discussion about those other models, fine, but that's not the discussion we're having.
However, by changing your assumptions you can still use O notation with more complex models.
So again, the issue is not that you can't compare numbers of arbitrary magnitude in constant time -- I never said that. The issue is that it is a contradiction to say that it takes linear time to inspect all the digits of a number AND that it only takes constant time to compare O(n) digits of two numbers.
You're essentially saying that you can axiomatize your mathematical universe with nonsense axioms, which yes, you could do, but that's not useful to point out.
Your statement was "If the numbers can be arbitrary in size, then you can't compare them in constant time". I was merely pointing out that this is not a true statement.
Again, for the third time: you cannot "assume" that reading the digits of a number takes O(n), but reading the digits of two numbers to compare them takes O(1). That is absolutely, obviously true. Your response, that you can "assume" the latter is true as part of the model of computation is just wrong, plain and simple. There's nothing else to say about it.
The original claim directly implies this, and if you can't address that point, then just save us both the time and don't respond.
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).
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)`).
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.
Moreover, that is essentially the whole point of the field of algorithms. Your job as an algorist is to abstract the algorithm away from the implementation details of wholly separate systems, and make all of your assumptions explicit. If you don't specify it, you can't analyze it. And, if an algorithm has to assume an entire, specific OS and scheduler is implemented under it, then you have gone about your job as an algorist completely wrong.
That is the appeal to practicality. But as if to prove my point, you _do_ end up making assumptions. You are assuming that the scheduler is backed by a priority queue, which is certainly not universally true. You don't get to a hard mathematical bound by waving away a detail as important as the data structure that backs the core sort mechanic. If your approach is to say "y'know, like a _normal_ scheduler", then you should stop and rethink your approach to the problem.
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
1) Shuffle the list.
2) If it's sorted, halt.
3) If it's not sorted, go to step 1.
1) Shuffle the list.
2) If it's sorted, halt.
3) If it's not sorted, destroy the Universe.
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.
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!
[1] https://www.kernel.org/doc/Documentation/timers/hrtimers.txt
https://github.com/majek/fluxcapacitor#basic-examples
$ ./fluxcapacitor examples/sleep_sort.sh 1 4 20 3 55
A paper is currently making the rounds, would love to hear feedback:
https://www.dropbox.com/s/zy1gx1azfvvqm6i/NetSciComm%20versi...
There's a reason 4chan should be considered a national...maybe not treasure, but it's pretty awesome.
Pretty sure it's been posted a couple other times, but I'm on a tablet at the moment.
http://perl6advent.wordpress.com/2014/12/23/webscale-sorting...
#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);
}
Example:
D:>sleepsort 1000 9 2 150 1 7 17 624
1 2 7 9 17 150 624 1000
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)I'm sad nobody has implemented my idea, rock, paper, scissors sort.
http://js.do/code/48526 (Optimized milliseconds). :)
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.
ruby -e '[3,1,2].each{|n| system("sleep #{n} && echo #{n} &")}'