An In-Place Sorting with O(n log n) Comparisons and O(n) Moves

Gianni Franceschini, Viliam Geffert
Journal of the ACM, Volume 52, Issue 4
Pages: 515 - 537
Year of Publication: 2005
http://doi.acm.org/10.1145/1082036.1082037

前任校でS君とソートのことをいろいろ考えていたためか，最近ソートにかなり興味が出てきた．
この論文はもう3年前 (FOCS会議バージョンは2003年なので5年前) だけども，作業領域O(1) (つまりin-place)，比較回数O(n log n)，要素移動回数O(n)という3つの尺度が同時に最適なアルゴリズムを提案している．
nが2の16乗以下の場合は何やってもよくて，nがそれより大きいときにどうするか，ということなので，今のところあまり実用的ではないでしょう．
それでも一見したところアルゴリズムは絶望的に複雑怪奇というわけでもなさそうなので，勉強がてら詳しくみてみたい気もする．
ただ，このアルゴリズムは安定ではないようなので，上記3つの計算量的要求と安定性を満たすアルゴリズムの設計が未解決問題として残されている，と本文が締めくくられている．