マージソート

　なにやら聞き覚えがあるなと古い本をひっぱりだすと確かにそこにあった。「応用 DISK BASIC 」アスキーラーニングシステムというシリーズの一冊として出版された。もはや入手は難しいであろうから一部引用してみる（マーケットプレイスで生き残っていたので驚き）。もっとも、マージソートというものそのものについてはどこぞかに説明が見つかるのだろうとは思うが。

　「応用 DISK BASIC 」によれば、マージソートはディスク上でファイルを直接ソートする方法として紹介されている。利点として、対象ファイルの大きさがメモリの大きさの制限を受けないとか、シーケンシャルファイルのソートが行えるとか、対象ファイルのレコード数が予想以上に増えてもプログラムの修正が必要ないなどがあげられている。

　欠点としては、ディスクに作業ファイルを作成するので、ディスクの残容量が必要であるとか、何度もディスクアクセスを行うので実行速度は遅い方法だとか。

　一例として紹介している「単純マージソート法」は次のような感じ。

1. ファイルを中央から２つのファイルに分割する。
2. 各ファイルから１つずつレコードを取り出し、それらをマージして長さ２のソート列（２つのレコードがソートキー順にならんでいる状態）からなるファイルを作成する。
3. 再びファイルの中央から２つのファイルに分割する。
4. 各ファイルから長さ２のソート列を取り出し、それらをマージして長さ４のソート列からなるファイルを作成する。
5. 以上の操作を繰り返すたびにソート列の長さが２倍となり、最終的にファイル全体がソートされる。

　例示されているイメージはこんな感じ。

a [ 10 8 3 9 20 1 15 ]
b [ 10 8 3 9 ] 　[ 20 1 15 ]
c [ [ 10 20 ] [ 1 8 ] [ 3 15 ] [ 9 ] ]
d [ [ 10 20 ] [ 1 8 ] ]　 [ [ 3 15 ] [ 9 ] ]
e [ [ 3 10 15 20 ] [ 1 8 9 ] ]
f [ [ 3 10 15 20 ] ] 　[ [ 1 8 9 ] ]
g [ 1 3 8 9 10 15 20 ]

　かつてメモリも少なくて、節約しながらやりくりしていた時代の産物なのかもしれない。とはいえ、考え方を知るのは無駄ばかりではないのだろうな。

「応用 DISK BASIC 」（戸内　順一、アスキー出版局、1984/8 発行、1900 円）
応用Disk BASIC―本格的パーソナル・コンピュータ利用への手引き
戸内 順一

　そういえば DISK BASIC には、merge コマンドがあったっけ。アスキーで発売したカード型データベースソフト「 88 カード」はマージしまくりのソフトだったなあと、ちょっと懐かしく思い出す。

追記 ( 2/26 )：タイトルを「マージ」から「マージソート」に変更。