Draft:Sleep sort

Sleep sort

Example of sleep sort sorting an array of random integers. The horizontal axis is the array index and the vertical axis is the integer.
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2}+max(input))$
Best-case performance	$O(max(input))$

Sleep sort is a time-based sorting algorithm, intended as a joke rather than as an algorithm for practical use, which has been posted to social media sites It works by associating a counter with each element to be sorted. Each counter is initially set with the value of the element to be sorted. The counters are then decremented at the same rate. When a given counter runs out, the associated item is added to the end of the list. Since the counters stop depending on the size of the elements, the list will be sorted once all the counters have stopped. This can be implemented using the operating system's timers, e.g. by forking a separate process for each element, or more simply using a vector of counters.

Code

There is a lot of discussion about the complexity of this algorithm. Although some believe that the complexity is $O(n)$ (considering that each element is visited only once), this algorithm abuses complex high-level routines that make its complexity more difficult to establish. The algorithm uses the sleep function, which puts a process to sleep by generating processor cycles or waiting for a condition to be met.

Bash

One version of the algorithm (written in bash shell script) is described below:

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

In this implementation, a function is responsible for printing the passed parameter --- which must be numeric and positive --- after waiting the same amount of time.

Python

By serialising the sleep function, the following code (written in Python) can be considered equivalent:

from time import sleep
from threading import Timer

def sleepsort(values):
    sleepsort.result = []
    def add1(x):
        sleepsort.result.append(x)
    mx = values[0]
    for v in values:
        if mx < v: mx = v
        Timer(v, add1, [v]).start()
    sleep(mx+1)
    print(sleepsort.result)

if __name__ == '__main__':
	sleepsort([7, 2 ,100, 1, 9, 45, 2, 33, 7, 77, 25])
	sleepsort([333, 222 ,112, 777, 901, 455, 256, 313, 125, 625, 825, 999, 316])

JAVA

public class SleepSort {  
    public static void main(String[] args) {  
        int[] ints = {1,4,7,3,8,9,2,6,5};  
        SortThread[] sortThreads = new SortThread[ints.length];  
        for (int i = 0; i < sortThreads.length; i++) {  
            sortThreads[i] = new SortThread(ints[i]);  
        }  
        for (int i = 0; i < sortThreads.length; i++) {  
            sortThreads[i].start();  
        }  
    }  
}  
class SortThread extends Thread{  
    int ms = 0;  
    public SortThread(int ms){  
        this.ms = ms;  
    }  
    public void run(){  
        try {  
            sleep(ms*10+10);  
        } catch (InterruptedException e) {  
            // TODO Auto-generated catch block  
            e.printStackTrace();  
        }  
        System.out.println(ms);  
    }  
}

Although theoretically correct, this algorithm should not be considered usable in real implementations because it presents several problems. The main one lies in the race condition that is inherent in its implementation. Without a doubt, if the values are too close to each other, the algorithm will not be able to sort the list satisfactorily, and the assumption that the data is always positive is a strong assumption because it implies that the interval in which the data is contained is known information.

Inspiration

The underlying mechanism of Sleep sort is similar to the Counting sort algorithm. This, also of O(n) complexity, instantiates an array the size of the largest element and then places each item in its respective position in the array. The resulting array is naturally sorted.