Sleep Sort: an amazing sorting algorithm!!

sleep_sort.py

#!/usr/bin/env python2.6
# -*- encoding: utf8 -*-

'''
An advanced version of Sleep Sort.

The original idea is from: http://coolshell.cn/articles/4883.html
Use the concept of radix sort to speed it up.

The newer version references WanCW's implementation in Ruby:
https://gist.github.com/1044476

This implementation only allows positive integers.
'''

import sys
import threading
import time
import Queue


__author__ = 'fcamel'


# The bigger, the faster. But a bigger value has higher risk to get incorrect results.
FASTER_RATE = 1000.0


def position(sleep_second, numbers, queue):
    time.sleep(sleep_second / FASTER_RATE)
    for n in numbers:
        queue.put(n)

def sleep_sort(numbers):
    def sort_a_round(numbers, index):
        buckets = [[] for _ in range(10)]
        for n in numbers:
            sleep_second = int(('%15s' % n).replace(' ', '0')[index])
            buckets[sleep_second].append(n)

        threads = []
        for i, ns in enumerate(buckets):
            th = threading.Thread(target=position, args=(i, ns, queue))
            th.start()
            threads.append(th)

        for th in threads:
            th.join()

        numbers = []
        while not queue.empty():
            numbers.append(queue.get())
        return numbers

    queue = Queue.Queue()
    max_n_digit = max(map(len, numbers))

    for i in range(1, max_n_digit + 1):
        numbers = sort_a_round(numbers, -i)

    return numbers

def main():
    if len(sys.argv) <= 1:
        return

    for n in sleep_sort(sys.argv[1:]):
        print n

if __name__ == '__main__':
    # Usage:
    #
    #     $ ./sleep_sort.py  23 20 25 512 987 98 5
    #     5
    #     20
    #     23
    #     25
    #     98
    #     512
    #     987

    main()