ストゥージソート
ストゥージソート(英: Stooge sort)は、再帰を用いたソートアルゴリズムのひとつである。
計算時間はO(n) = O(n)であり、これはマージソートなどの効率的なアルゴリズムよりも、それどころか非常に効率の悪い単純なソートの例としてよく挙げられるバブルソートよりも遅い。
アルゴリズムは以下の通りである。
もし末尾の値が先頭の値より小さければ、それらを入れ替える。
現在処理している部分列の要素数が3以上であれば、 リストの先頭2/3に対してストゥージソートを行う。 リストの末尾2/3に対してストゥージソートを行う。 リストの先頭2/3に対して再びストゥージソートを行う。
そうでなければ終了。