最近ぼつぼつと読んでいる本*1の中で紹介されていたソート。要素同士を全部比較しておいて、それぞれの要素について自分より小さい要素の数を数える。そういう要素がn個あったら、ソート結果では自分はn+1番目になる、というもの。なるほど、言われてみれば確かにその通り。
全要素が異なる場合に使えることは明らかなんですが、等しい要素があっても大丈夫なようにもできる、とのこと。人間がこんな風にソートをすることはありえないけど、コンピュータ向きの単純な作業の繰り返しですね。このアルゴリズム、実用的なものではなく、演習問題的にとりあげられているもののようです。
しかし、この手法、なんで今まで知らなかったのか。
