スターリンソートよりも速いO(1)のソート

はじめに

みなさん、スターリンソートはご存じですね？

以下のツイートが有名でしょう。

ソートされていない要素を粛清することで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)のアルゴリズムです。
そこで、次のようなアルゴリズムを提案します。

アルゴリズム

アルゴリズムは簡単。

いかなる入力に対しても、あらかじめ用意したソート済み配列（リスト）を返す。

これだけです。これなら問題なくO(1)を達成できますね。

実装

では早速実装していきましょう
まずはRubyから

sort.rb

module Mod
  SORTED = (1..10).to_a
  def sort(arr)
    SORTED
  end
end  

result.rb

> sort([1, 2, 3])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

続いてC#

sort.cs

namespace MySort {
  public static class MySort {

    public static readonly int[] Sorted = Enumerable.Range(1, 10).ToArray();
    public static int[] Sort(int[] arr)
    {
      return Sorted;
    }
  }
}

result.cs

> MySort.Sort(new int[] { 1, 2, 3 })
int[10] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

最後にHaskell
これだけ空リストが来たときだけはお情けで空リストを返すようにしてあります

sort.hs

module MySort where

sort    :: [Int] -> [Int]
sort [] = []
sort xs = [1 .. 10]

result.hs

> sort [1, 2, 3]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

まとめ

スターリンソートよりも高速なソートアルゴリズムを提案しました（ソートできるとは言ってない）
問題は名前ですが、「真実を握りつぶしあらかじめ決められた情報を流す」というイメージから

大本営発表ソート

なんてどうでしょう。大本営発表を英語にすると "Imperial Headquarters announcement" なのですが、長いので "Propaganda Sort" (プロパガンダソート) とかでもいいと思います。