やさしいスターリンソート入門【実用的】 - Qiita

def gentle_stalin_sort(arr): siberia = [None] * int(max(arr) + 1) for n in arr: try: siberia[int(n)] = n except: pass # siberiaに送れないnは粛清 return [n for n in siberia if n is not None] # n>0なら if n だけでよい a = [5, 3, 4, 0, 2, 1] gentle_stalin_sort(a) すてき！ え？ Nが大きな値の時はどうするのか？ シベリアは広大なので、そんなことは気にしません。 計算量 やさしいスターリンソートのソースを見ると、一重のループしか存在しません。 実際、ちゃんと実装をすれば時間計算量のオーダーは O(len(arr) + max(arr)) で済みます。すごい！ ただし、

[igrep]

“え？ Nが大きな値の時はどうするのか？ シベリアは広大なので、そんなことは気にしません。”

[ooblog]

#富豪プログラミング #バケットソート 「データの値がNであればシベリアのN番地に送る~重複しているキーがある場合~空間計算量がmax(arr)*len(arr)のオーダーに」

[keint]

基数ソート的な考え方かなって思った

[about42]

全ては広すぎるシベリアが悪い