話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装したというネタがあったので乗っかります。
元ネタは
ソートされていない要素を削除（粛清）して、強引に昇順リストを生成
というものですが、率直に言ってスターリンはまだ甘いです。
まず、ソート結果にも複数の要素が含まれてるということは、変更を加えられて再度、ソートされていない状態になる可能性を残してしまいます。
さらに、そのような不完全さを残しているにも関わらず、これにはO(n)もの時間がかかってしまいます。
こんなことでは真の独裁は維持できません。
さて、どうしたものか。
ということで、困ったときはドラえもんです。
かの有名な「どくさいスイッチ」を参考にしましょう。
最後にのび太が1人になる(いや、まあ、現実にはごにょごにょなんですが)アレです。
はい、オートクラシーソート！
autocracySort :: [a] -> [a]
autocracySort [] = []
autocracySort (x:_) = [x]
print $ autocracySort [1, 2, 3]
-- => [1]
print $ autocracySort [9, 234, 23, 2, 1, 93]
いくつ要素が含まれていようが、最初の1要素だけを含んだリストを返します。
ソート結果が正しいことも簡単に確認できる完璧なソートです。
そして何と計算量オーダーはO(1)です。
print $ autocracySort [n * n | n <- [1..]]
-- => [1]
さらに何と無限リストも扱えます。
これなら無限に湧いてくる聞き分けのない市民がいても、安心して独裁生活を送れます。
では、みなさん、良い独裁ライフを！