← Back to home

Sleep sort

💬 15 comments
#General

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.

Comments (15)

Julien Ponge

Awesome... and it works :-)

Cedric

Well... kind of. There are a lot of situations in which it won't work, enumerating these might be fun.

Justin Lee

Like sorting negative numbers and floating points. :)

Dave

It's very slow for large values, so I suggest dividing your array by a huge value before sorting....or not. >:)

Daniel Spiewak

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.

Sanjar Akhmedov

This sort delegates actual sorting to the scheduler. I think average complexity is heap alike.

daehbe

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

Jewel

Awesome!

Blusky

But it you try to order a huge amount of small number, it won't work

Bob Lee

http://gafter.blogspot.com/2006/11/linear-time-sort-puzzler.html :-)

Wotan

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?).

Craig Tataryn

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 :)

Jens

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.

Xamuel

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.

Anon

You got this from dis.4chan.org