1.2 マージソート 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム



  • O(n log n)時間でのソート。この時間は、ソート対象列のデータ型・データ構造の条件を用いない場合には、最短なものの1つ。
  • 本項中のその他の記述。「任意の再帰アルゴリズムを計算時間を増加させることなく、再帰呼び出しなしのアルゴリズムで書ける」
  • リストを同長の2つのリストに分割する。その上で、2リスト要素の順序関係を逐一確認する
  • ここで用いる「2つのリスト」の2とはどういう数だろうか?2が特殊な数であることは確かだが、それは、分割することができる最小数という意味での特殊性だろうか、それとも別の意味があるのだろうか。すぐには思いつかない。
  • 本書での証明は、分割数2について、その処理オーダーを帰納法にて、k n log(n) + (より低オーダーの項)、であることを示している。この証明法で見る限り、分割法によらず、オーダーとしてはn log(n)で押さえられるように見えるが・・・2分割にするほうが(n/2)ペアに分割するより効率的だろうから、この証明法で丸められている部分の異同が、至適分割数に関する情報になるのだろうな、というところまではおそらく正しい
  • A sorce by "Dickinson College, Fall Semester 2002, Grant Braught" is here.