#初めに
随分前のものになるが、スターリンソートなるものを見た。
そして、これよりも計算量が少なるソートを考えてみた。

その名も、切り捨てソート
計算量が少ないのかは知らんが。
#切り捨てソート
切り捨てソートとは強引にソート(昇順)にさせる。
その名の通り、昇順になっていない要素があったら、その後ろの値全てを粛清する。
昇順になってさえいればソートである。(暴論)

def CutSort(L):
    R=[]
    imax=-1
    for i in L:
        if imax<i:
            R.append(i)
            imax=i
        else:break
    return R

入力:[4,8,9,10,4,6,7,2]
出力:[4, 8, 9, 10]

いい感じだ。
一つでも不適格なのがあるとその後ろを見ずにバッサリと切り捨てる。
なんと素晴らしいソートであろうか。

こう考えるとまだ全体をみてやるスターリンソートのほうが優しいのかもしれない。