Efficient sample sort and the average case analysis of PEsort

Jing-Chao Chen
Theoretical Computer Science
Volume 369, Issues 1-3 , 15 December 2006, Pages 44-66
http://dx.doi.org/10.1016/j.tcs.2006.07.017

著者が2001年 (SICOMP) に提案したPEsort (proportion extend sort) の解析に関する論文．
このアルゴリズムではパラメータpを用いて，入力の既にソート済みの部分Sとソートが済んでいない部分Uを考えて，(S,U)の上で動く．
(つまり，ソートするためには，入力全体をUとし，Sは空であるとしてアルゴリズム実行を開始すればよい．)
アルゴリズムの概観は以下の通り．

まず，入力のサイズが1なら終了．そうでない場合がメインである．
ここで，Sの大きさがS+Uの大きさをp(1+p)で割ったもの以下である限り以下を繰り返す．
はじめに，Uの中からSの大きさのp倍だけ要素を取ってくる (U'とする)．
そして，(S,U')を (再帰的に) ソートする．
その結果を新しくSとして，U-U'を新しくUとする．
以上で繰り返し終わり．
その次にSの中央値mを用いてUをmよりも小さい部分ULとmよりも大きい部分URに分ける．
Sもmより小さい部分SLと大きい部分SRに分ける．
そして，(SL,UL)と(SR,UR)を再帰的にソートする．
そして，(SL,UL)のソート結果とmと(SR,UR)のソート結果を順に並べればソート完了である．

これはquicksortに若干似ている．しかし，最悪時間計算量を考えるとquicksortではO(n^2)になってしまうのに対して，PEsortはO(nlogn)になる．
未解決だったのは，平均時間計算量の方．
Cole & Kandathil (ESA 2004) はp=1の場合に平均時間計算量がO(nlogn)となることを示した．
この論文では任意のpに対して平均時間計算量がO(nlogn)となることを証明している．
その解析のためにfull sample sortというものも提案している．