はじめに

昇順（降順）になっていない要素を粛清する（取り除く）ことで$O(n)$の計算量を実現したソートアルゴリズム？
去年話題になったらしいが、自分は出会わなかった。

Python3.8以降ならすごくスッキリ書ける。

実装

stalin_sort = lambda x:[m:=x[0]] + [m:=i for i in x[1:] if i>=m]

arr = [1, 2, 1, 1, 4, 3, 9]
print(stalin_sort(arr))
# ---> [1, 2, 4, 9]

print(len('lambda x:[m:=x[0]] + [m:=i for i in x[1:] if i>=m]'))
# ---> 50

粛清というより存在を無視する感じの実装になったが短くてステキ