ジョークプログラム(sleep sort)

sleep sortなるものを実装してみた。
元ネタはここGenius sorting algorithm: Sleep sort
消えてると寂しいので一応引用。

Genius sorting algorithm: Sleep sort
1 Name: Anonymous : 2011-01-20 12:22
    Man, am I a genius. Check out this sorting algorithm I just invented

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

    example usage:
    ./sleepsort.bash 5 3 6 3 6 3 1 4 7
2 Name: Anonymous : 2011-01-20 12:27
    >>1
    Oh god, it works.

    But I don't like to wait 218382 seconds to sort '(0 218382)
3 Name: Anonymous : 2011-01-20 12:31
    >>2
    yes the worst case is very big

まぁ、要素ごとにスレッドを止めて終わった順に値を表示するだけ。
Sagittariusで書いてみた。append!が破壊的かつSRFI-18をサポートしてる処理系なら何でもいけるはず・・・

(library (sleep-sort)
    (export sleep-sort)
    (import (rnrs) 
            (srfi :1)
            (srfi :18))
  (define (sleep-sort lst)
    (let* ((new (list '()))
           (threads (map (lambda (e)
                           (unless (integer? e)
                             (assertion-violation 'sleep-sort
                                                  "integer required but got" e))
                           (make-thread (lambda ()
                                          (thread-sleep! e)
                                          (append! new (list e))
                                          e)))
                         lst))
           (r (map thread-start! threads)))
      (map thread-join! r)
      (cdr new))))

こんな感じで使う

(import (sleep-sort))
(print (sleep-sort '(5 4 6 2 8 9)))
;; => (2 4 5 6 8 9)

上記のコメントにもある通り、最悪時間(というか計算時間？)は要素内の最大値になるので、馬鹿でかい数値だと10分くらい返ってこないとか普通にありえるので要注意。(ソートが終わらないから仕事ができないという言い訳にはなるけどｗ)

追記：
びっくりするくらい2番煎じだった件・・・ scheme(gauche)でもsleep-sort