Sleep Sorting in Python, using Threads

In [here], an unusual, fun sorting algorithm, called ‘Bogo’, is demonstrated using Python. This article, which introduces another famous sorting algorithm, which may be just for fun only. The name of the sorting algorithm is called “sleep sort”. The basic idea is that, sleep some interval according to the value and print out. For example, if you want to sort the array [3, 1, 2], you can create three threads, which sleep 3, 1 and 2 seconds respectively. After the interval, the threads are to output the value, which will be in the order of 1, 2 and 3.

The space complexity is because no additional space needs to be allocated for this algorithm. The python code can be downloaded at [github]

#!/usr/bin/env python

import threading
import time
import random

# lock array
_lk = threading.Lock()
# sorted array
_ar = []

class SleepSortThread(threading.Thread):
    """
        SleepSort Thread
        acm.steakovercooked.com
    """

    # constructor
    def __init__(self, val):
        self.val = val
        threading.Thread.__init__(self)        

    # thread entry
    def run(self):
        global _lk, _ar
        # sleep corresponding interval
        time.sleep(self.val * 0.1)
        # lock before append
        _lk.acquire()
        _ar.append(self.val)
        _lk.release()

def SleepSort(x):
    global _ar    
    ts = []
    # create threads
    for i in x:
        t = SleepSortThread(i)
        ts.append(t)

    # start threads
    for i in ts:
        i.start()

    # wait till all finished
    for i in ts:
        i.join()

    # return sorted array
    return _ar

if __name__ == "__main__":    
    x = range(30, 40)
    random.shuffle(x)
    print "before = ", x
    t1 = time.time()
    x = SleepSort(x)
    t2 = time.time() - t1
    print "after = ", x
    print "time = %.3f seconds" % t2

The above prints the following:

before =  [38, 31, 37, 36, 34, 35, 39, 32, 30, 33]
after =  [30, 31, 32, 33, 34, 35, 36, 37, 38, 39]
time = 3.901 seconds

It is noted that an lock is used to prevent multiple threads appending elements to the sorted array simutanenously, e.g. It is more likely to happen if identical elements appear more than once in the array.

–EOF (The Ultimate Computing & Technology Blog) —