スリープソート

スリープソート（英語：sleep sort）とは、究極のソートアルゴリズムである。

概要

アメリカの巨大掲示板群である4chanのプログラミング板にて「Genius sorting algorithm: Sleep sort」というスレッドが立てられた。2ちゃんねる風に訳すと「ちょwwwすごいソートアルゴリズム思いついたwwwww」といった感じである。

#!/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

あまりの凄さに全米が震撼した。 スリープソートは数学的概念を覆し、精度方向にスケーラブルであり、個々が独立しているため超並列も可能である、など様々な特徴を持っている。 このスリープソートを半導体で実装し、1クロックを1スリープとし、GPUのシェーダーばりに超並列とすれば爆速ではないかなど様々な議論を呼んだ。

初期実装における難点は数値しか扱えないことであったが、コンピューター内部では全てを数値として表すため不可能はなく、後に登場した実装ではあらゆるデータをソートできるようなものも登場している。

ちなみに2007年に日本人で同様のアプローチで「ショットガンソート」と名付けてほぼ同様のアルゴリズムを実装した方がいる。

主な実装

スリープソートの発想の画期的さと実装の容易さから瞬く間に様々なプログラミング言語による実装が登場した。

関連項目

• ソート