It’s not very often that someone invents a new sort, but I have certainly never seen that one before:
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
The idea is simple: you take the first element of the array, say n, you fork a new process which sleeps n seconds then displays that number. Repeat for the next element.
Calculation of the average complexity of this algorithm left as an exercise to the reader.
Related: Quantum bogosort.
For some reason, I feel like taking a nap.
#1 by Julien Ponge on June 15, 2011 - 10:49 am
Awesome… and it works 🙂
#2 by Cedric on June 15, 2011 - 10:50 am
Well… kind of. There are a lot of situations in which it won’t work, enumerating these might be fun.
#3 by Justin Lee on June 15, 2011 - 11:03 am
Like sorting negative numbers and floating points. 🙂
#4 by Dave on June 15, 2011 - 11:03 am
It’s very slow for large values, so I suggest dividing your array by a huge value before sorting….or not. >:)
#5 by Daniel Spiewak on June 15, 2011 - 11:42 am
From a theoretical standpoint, this isn’t actually a new sort. It’s a disguised version of bucket sort, albeit a *very* clever encoding. It certainly made me smile.
The answer to the reader exercise is that the complexity of this algorithm is O(m+n), where m is the largest numeric value in the sequence. This is reflective of the fact that it is just bucket sort with a very clever skin.
#6 by Sanjar Akhmedov on June 15, 2011 - 8:04 pm
This sort delegates actual sorting to the scheduler. I think average complexity is heap alike.
#7 by daehbe on June 15, 2011 - 9:14 pm
it looks hahaha, but …
./sleepSort 0.001 0.0011 0.00011 0.0001
0.001
0.00011
0.0001
0.0011
./sleepSort 0.001 0.0011 0.00011 0.0001
0.001
0.0011
0.00011
0.0001
#8 by Jewel on June 15, 2011 - 9:16 pm
Awesome!
#9 by Blusky on June 16, 2011 - 2:55 am
But it you try to order a huge amount of small number, it won’t work
#10 by Bob Lee on June 16, 2011 - 5:00 pm
http://gafter.blogspot.com/2006/11/linear-time-sort-puzzler.html 🙂
#11 by Wotan on June 17, 2011 - 1:41 am
I guess complexity in this case is O(n^2). The key point is the call to sleep, whose complexity I don’t know, but I guess it’s O(n) (perhaps the same as the scheduler of the operating system?).
#12 by Craig Tataryn on June 17, 2011 - 8:21 am
It reminds me of a sorting exercise (can’t remember which book it was) where you put numbers on the sides of identical cars, and then fill their gas tank proportional to the number written on the side of the car. Then you get up on a tall building and tell the drivers to start driving. At the end of it all, the cars should all be sorted by their number (lower numbered cars ran out of gas first). That actually has a complexity of O(1) 🙂
The funny thing is, sleep sort still has a complexity proportional to input size of O(n) (or big-theta(n)) because you only iterate through the input once.
One of the situations where this would fail is when the number of input values is really big and small numbers appear at the end of the input:
1,2,3,4,………….,1
So executing sleep sort on a computer might take longer than 2 units of time to “get to” the last 1 in the list, at which point it already has displayed the number 2. Of course, this is machine dependent and probably wouldn’t even factor into a “proper” complexity analysis 🙂
#13 by Jens on June 18, 2011 - 8:44 am
Ever heard of deletion sort? Delete all elements except two. The remaining list is sorted, but you don’t now if ascending or descending. Delete all elements except one and the list is sorted in both directions.
#14 by Xamuel on June 18, 2011 - 3:00 pm
This should be renamed “Apache Sort”, as I’m sure it’ll be what the Apache dev team uses to sort everything as soon as they become aware of the algorithm.
#15 by Anon on June 19, 2011 - 6:14 am
You got this from dis.4chan.org