はてなブックマーク

はじめに みなさん、スターリンソートはご存じですね？ 以下のツイートが有名でしょう。 ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる — やんぎん (@4116You) July 28, 2019 Qiitaの記事では 計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell https://qiita.com/Tatsuki-I/items/380d6bd06515b872b2b2 や 計算量O(n)で噂のスターリンソートを実装してみた https://qiita.com/MeilCli/items/721526d716851e92192a などが有名ですね。 しかし、これでもまだO(n)にしかなっていません。我々が目指すべきはO(1)のアルゴリズムです。 そこで、次のような