- 著者
-
萩原 洋一
池田 論
中森 眞理雄
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.98, no.442, pp.57-64, 1998-12-04
- 被引用文献数
-
1
1
マージソートは時間計算量が0(n log n)(nはソートされるレコードの個数)であり高速であるが, 内部ソートとして実行する場合, 作業場所として大きさnの配列を要するのが欠点であるとされている.本論文では, 作業場所として数語だけを要するマージソートを提案する.新しいマージソートの時間計算量は0(n log^2 n)であり, 従来のアルゴリズムより悪いが, これは作業場所とのトレードオフの結果である.