常識を覆すソートアルゴリズム！その名も"sleep sort"！

neta

TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。
Genius sorting algorithm: Sleep sort

1 Name: Anonymous : 2011-01-20 12:22
諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？

#!/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
なん…だと…。こいつ、動くぞ！

っておい！0..218382のリストのソートに218382秒も待たされるのかよ！

3 Name: Anonymous : 2011-01-20 12:31
>>2
まあ、最悪のケースだとそうなるな。

4 Name: Anonymous : 2011-01-20 12:45
これの計算量はどんなもんだろう？

5 Name: Anonymous : 2011-01-20 12:56
#!/bin/bash
function f() {
    sleep $(echo "$1 / 10" |bc -l)
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

最適化に成功したぞ！
ただしsleepが浮動小数点数を受け付けるシステムじゃないと動かないので注意な。

6 Name: Anonymous : 2011-01-20 13:10
>>4
そうだな…正直よくわからんが、O(入力値の中の最大値)なんじゃないか。

7 Name: Anonymous : 2011-01-20 14:16
O(入力値の中の最大値 + n)じゃないかな。スレッドの生成に比例した時間が余計に掛かるだろ。
しかしこれはすばらしい。

...

これは面白い！まさかsleepを利用してソートができるとは！実行してみると確かに値がソートされていることがわかる。スレッドはこのあともしばらく続き、C#・Erlang・Lisp・C・Perlなどの言語でも実装されたようだ。
せっかくなので私もPerlで実装してみた。上記掲示板でのオリジナル実装とは異なり、サブルーチンとして独立させているので汎用的に使える。

#!perl
use strict;
use warnings;
use Time::HiRes qw(sleep);
use IO::Select;

use Data::Dumper;

sub sleep_sort {
    my @input = @_;
    my @output;
    my $watcher = IO::Select->new();
    my @children;

    foreach my $value(@input) {
        my $pid = open my $io, '-|';
        defined($pid) or die $!;

        if($pid == 0) {
            sleep $value / 10;
            print $value;
            exit;
        }
        else {
            $watcher->add($io);
            push @children, $pid;
        }
    }

    while($watcher->count > 0) {
        foreach my $io( $watcher->can_read(0) ) {
            $watcher->remove($io);
            push @output, <$io>;
            close $io;
        }
    }

    waitpid $_, 0 for @children;

    return @output;
}

print Dumper([ sleep_sort @ARGV ]);
__END__
$ perl sleep-sort.pl 1 3 5 2 4
$VAR1 = [
          '1',
          '2',
          '3',
          '4',
          '5'
        ];

スレッドやファイバを使っても実装できるだろうが、今回はopen()によるforkとIO::Selectを使ってみた。