任意の外部記憶容量で動作するマージソート

摘要

ソート対象の要素数と等しい外部記憶領域を必要とするマージソートアルゴリズムを，任意の大きさの外部記憶領域で実現できるように改良したアルゴリズムを提案する．同様の改良例は様々に存在するが，本提案はべ－スアルゴリズムの基本特性をほぼそのまま受け継ぎ，実質的な計算量もほとんど劣イヒさせずに実現した方式である．本論文では，乱数列をソートする実験により有効性の検証も行う．