Introduction

Sleep sort is a very curious and original algorithm. It brings several interesting questions. Such as, how to measure its complexity or in what cases does it perform the best.

Principle

In a nutshell: for each element to sort, start a thread or a process which sleeps a time proportional to the element and then pushes it back to the main thread.

Trivial Bash implementation:

1
2
3
4
5
6
7
8
9
10
11
12

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

Test suite

In order to study it and measure its performance we (me and Hartok) decided to implement the Sleep Sort in Python and gevent.

Our program generates a set of random numbers and sorts it with Sleep sort then with the Python built-in Quick sort and records timings. It works with three parameters:

  • set size
  • maximum value in the set
  • the ratio between sleep time and values in the set (for example with 10 the thread for 42 sleeps for 42/10 seconds)

This last parameter is pretty tricky: the higher it is, the faster the Sleep sort works. But if it is too high, the time to start a new thread (or greenlet) will be more important than the sleep time for low values and the result will be incorrect. It seems to be strongly hardware dependent and a little tied to the other parameters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#!/usr/bin/python
 
import sys
import random
import time
import copy
import gevent
 
divisor = 900000
 
def sort(numbers):
        """ Sorts a list with Sleep Sort algorithm and measures time
        """
        begin = time.time()
 
        def f(n, result):
                gevent.sleep(float(n)/divisor)
                result.append(n)
        
        result = []
        greenlets = []
        # spawn a sleep greenlet for each value
        for n in numbers:
                greenlets.append(gevent.Greenlet.spawn(f, n, result))
 
        # wait for all greenlets to end
        gevent.joinall(greenlets)
        return (time.time()-begin, result)
 
def systemsort(numbers):
        """ Sorts a list with system sort function and measures time
        """
        begin = time.time()
        result = copy.copy(numbers)
        result.sort()
        return (time.time()-begin, result)
 
def generate(n, m): 
        """ Generates a list of n random numbers, each being less than m
        """
        numbers = []
        for i in range(n):
                numbers.append(random.randint(1, m))
        return numbers
 
if __name__ == '__main__':
        # read params
        try:
                n = int(sys.argv[1])
                m = int(sys.argv[2])
        except BaseException:
                print "usage: %s n m [d]" % sys.argv[0]
                print " - n number of random numbers"
                print " - m maximum random value"
                print " - d time divisor (optionnal), default is %d" % divisor
                sys.exit(1)
 
        try:
                divisor = int(sys.argv[3])
        except:
                pass
 
        # generate random values
        numbers = generate(n, m)
        # sleep sort them
        (sleep_time, sleep_result) = sort(numbers)
        # system sort them
        (system_time, system_result) = systemsort(numbers)
 
        if system_result == sleep_result:
                print "sleep sort succeed"
                print "sleep: %f" % sleep_time
                print "system: %f" % system_time
        else:
                print "sleep sort failed (time divisor too ambitious ?)"
                print "sleep: (%d elements)" % len(sleep_result)
                #print sleep_result.__str__()
                print "system: (%d elements)" % len(system_result)
                #print system_result.__str__()
                errors = 0
                for n in range(n):
                        if system_result[n] != sleep_result[n]:
                                errors = errors + 1
                print "%d errors" % errors

Test results

quicksort.png

sleepsort.png

ratio.png

The overall performance of the Sleep sort is awful, but it has interesting performance when it comes to sets with few different values.