8【ネタ】O(1)のソートアルゴリズムPythonネタはじめにある日、こんな記事を見つけた。スターリンソートよりも速いO(1)のソート「真実を握りつぶしあらかじめ決められた情報を流す」といったことから大本営発表ソートと名付けられたこのソート、なんか面白そう。他にもないのか調べたら、色々見つけたのでまとめる。3]まあそうなるなって感じのアルゴリズムですね。オートクラシーソートオートクラシーソートを発見。7]出力[3]大本営発表ソートと比べて、一応元の配列の考慮をしている。計算量も$O(1)$。スピリチュアルソートこのソートはKuina-Chanのサイトに上がっていた。「スピリチュアルソート」というアルゴリズムを思いつきました。順番に並んでいないデータ列に対して、「順番に並んでいるんだ...」と深く信じることで、なんと順番に並んでいるかのように思えてしまうO(1)の奇跡のアルゴリズムなのです。7]このソートアルゴリズムすごいですね。順番に並んでいるのがよくわかります。え?順番に並んでない?何を言ってるんですか?よく見てくださいよ。並んでいるじゃないですか。わかりませんか?このままでは新規性がないこのまま終わるとただ他人の褌で相撲を取っているだけなのでよろしくない。いうわけでなんか考える。要件は以下の一つだけ!$O(1)$であること。無理ゲーすぎるのでは?頑張って一つだけ思いついた。名付けて検閲ソートです。検閲ソート正直、大本営発表ソートの発表する内容が変わっただけなので新規性としては微妙なのですが、これしか思い浮かばなかったです。入力を受け取ると、手始めにすべて握り潰す。握りつぶした後で、検閲したことと空になったリストを表示する。これを実装するとこんな感じになる。reasons.[]要素を全部消し飛ばしたので当然ソートできてるし、無限長の長さの配列を持ってこられたところで出力は同じなので$O(1)$です。