4chan 上有个家伙发帖说他发明了一种很牛叉的排序算法：睡眠排序（Sleep Sort）：

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

主要就是对输入的每一个数都新开一个进程，进程里用这个数进行倒数，倒数到0就输出这个数。于是较小数就先输出、较大数后输出。睡排成功～

当然啦群众的眼睛是雪亮的，纷纷指出这个会存在竞态条件，而且如果的数比较大会很悲催（比如要排的数字里有86400的话，那么至少要等86400秒，也就是一整天 =。=），时间复杂度是 O(最大的那个数)……

在这个欢乐的帖子里还看到了各种其它语言对睡眠排序的实现，包括一个 Lua 的（#165）：

#!/usr/bin/env lua
function sleepsort(arr)
    local res, thread = {}, {}
    local nthreads = #arr

    for i = 1, #arr do
        thread[i] = coroutine.create(function()
            for n=arr[i], 0, -1 do coroutine.yield() end
            nthreads = nthreads - 1
            thread[i] = nil
            res[#res+1] = arr[i]
        end)
    end
    while nthreads > 0 do
        for i = 1, #arr do
            if thread[i] then coroutine.resume(thread[i]) end
        end
    end
    return res
end

math.randomseed(os.time())
local arr = {}
for i = 1,10 do arr[i] = math.random(1,99) end
print(unpack(sleepsort(arr)))

嗯哼～ Lua 的 coroutine 还是很强大滴（<ゝω·）

p.s. 终于还是见识到了最无厘头撞大运的 Bogo 排序算法：

while not inOrder(deck) do
    shuffle(deck);

Lua算法Linux