照山, 順一   岩間, 一雄   
数理解析研究所講究録 2040 35-42 2017年7月
比較ソートにおける効率は主に比較回数によって計られる. 本研究では, できるだけ平均の比較回数が少ない比較ソートアルゴリズムの設計を目的とする. EdelkampとWeiβによってFordとJohnsonのアルゴリズムの平均比較回数がnlgn-1.3999n+O(lgn)であることが示されている. また, 情報理論的下限から平均比較回数の下限はlceil lgn!rceil approx nlgn-1.4426n+O(lgn)であることが知られている. 本研究では, 2つの要素を挿入する操...