メモリに収まらない数量のソートが必要ならマージソートと組み合わせよう

悶絶しそうなコードを先日見たのでネタにさせていただきます。
どのように悶絶しそうになったかを書くとその人にバレるので話を一般化したうえでさらに別の例で当人にはまったく気づかれない話題に仕立てます。

膨大な量をソートしなくてはならず、メモリ量の制約から一括して行えない場合は分割してソートすればいいですよ、というお話です。

といっても、話は非常に簡単です。手順はこうです。

第一段階

1. 残っている(初回なら先頭からの)未ソートのデータをとりあえずメモリに収まる分だけの量をソートします。ソートアルゴリズムは何でもいいです。クイックソートのライブラリはC言語にすらありますので適宜利用してください。
   この際に使用するソート用の比較条件は第二段階で使いまわします。
2. 1でソートした内容を、それぞれ個別にファイルに吐きます。便宜的にこれらのファイルをζとします。
3. データが尽きたら第一段階を終了し、第二段階に進みます。
4. 1に戻る。

第一段階おわり。

第二段階として、いっぱいできているはずのファイルζをマージソートしていきます。

1. 一つもファイルζがない場合は第二段階を終了します。
2. 2つずつファイルζを開いて(便宜的にそれぞれa,bとします)、先頭から第一段階の1.でソートに利用したしたのと同一の比較条件に合致したデータを別ﾌｧｲﾙ(便宜的にcとします)に吐いていきます。
   aしか開けない(bがない、つまり最後の一つの)場合、aをそのままcにリネームし、第二段階を終了します。
3. a,bどちらかのファイルが終端になったら、まだ終端に達していないほうの残りのデータをすべてcにコピーしたうえで、a,bの両者を削除します。
4. 1に戻る。

第二段階が一回おわると、cが第一段階で出来たファイルζの半分の個数できているはずです。
ここで出来たファイルcをファイルζとみなし、また第二段階先頭に戻り、処理します。
これを繰り返し、最後にファイルcが1つだけになったらソート完了です。

これは基本中の基本なのでこの程度は当然思いつくと思います。
この工夫を考え付く人なら、以下は必要ないでしょう。
しかしながら、経験上、ファイルを扱う際に以下に述べる程度の工夫をしない人も多数見受けられ、絶句することがあります。
多分言語側がすべてやってくれるんだと過度の期待をしているものと思いますが、そもそもなーんにも考えてない可能性もあります(そうとしか思えない人が多すぎる(そしてそういう人に限って声だけ大きい))。
簡単ですが効果ある手法をご紹介します。
言語によらず、せめてこのくらいは最低限行いたいところです。

一つ。ﾌｧｲﾙIOはシーケンシャルアクセスになるように設計しましょう。
ランダムアクセスのほうが早い外部記憶装置(HDDやSSDなど)は存在しないからです。
一般的にHDDだけでなくSSDでさえシーケンシャルアクセスのほうが圧倒的に早いです。
いくらアルゴリズムを見直しても、どうしてもファイルに対してランダムアクセスをしなくてはならない状況に陥ったら、十分な大きさのメモリマップトファイル(posixならmmap,Win32APIならCreateFileMapping,javaならFileChannel,csharpならMemoryMappedFile)の利用を検討してください。
とはいえ、結局マップしなければならない箇所がコロコロかわるなら、効果は限定的です。出来ればマップ元データの構造の再検討をお勧めします。

一つ。ファイルIOの発生は極力控えましょう。
一般的に、ハードディスクはシーケンシャルアクセスであっても、いくら早くても転送速度は250MB/s程度です。大量のHDDでRAID0を組んで(ストライピングして)涙ぐましい努力を重ねても1GB/sなんてとてもではないけど届きません。
一方、メモリは今時古臭いDDR3-1600なシングルチャネルであっても12.8GB/s、ふつうはデュアルチャネルな仕様のマザーボードが多いでしょうから25.6GB/sの速度です。
まあ、比較にならない速度です。
従って、まずは本当に外部記憶に頼る必要があるのか、採用しようとしているアルゴリズムをよく見直してください。
そのうえで、どうしても必要ならメモリが許す限り先読み用バッファと書き込み用バッファを十分な量確保したうえでｼｽﾃﾑコール発行回数を極力減らしてください。
数バイトずつread/write(posix), ReadFile/WriteFile(Win32API)するなんて愚の骨頂です。最近の言語はよくできていて、大抵はリードバッファ、ライトバッファ付きのストリーム操作手段が用意されているはずです。たとえばcsharpだったらFileStreamのコンストラクタでバッファ量を指定できますしjavaならBuffered[Reader|Writer]で同様のことができます。C/C++ならmalloc()/newで自力で管理する必要がありますので、どうせライブラリが充実している言語を使うなら、その恩恵を十二分に享受したほうがお得です。というよりも、意識して使ってください。

一つ。開いたファイルは閉じましょう。
ガベージコレクタがいずれは閉じてくれるからいいって?
ほんとに?
忘れてただけなんじゃないの?!

一つ。OSが管理する資源には最後には結局OSのAPIがcallされます。
ファイルだろうがTCP/IPによる通信だろうがスレッド生成だろうがプロセス生成だろうが同じことです。
結局どんな高級言語でもどんな資源をどのように扱うのかを、きちんと最終的にはOS側のAPIが呼ばれてどうなるか理解したうえで設計しないとロクなもんにならんから油断しちゃいけないです。
たとえば身近なところではスレッド。余程の事はない限り必ず使うでしょう。
でも何かを勘違いしている人は声が大きい。たとえばcshrapならマルチスレッド処理にはイマドキThreadよりTaskを必ずつかえとか。でもGUIスレッドで時間のかかる処理を行うと動作が固まるので重い処理を行うワーカースレッドを起動して、GUIではそのワーカースレッドの進捗を表示するという場合も多いと思います。この場合、メインスレッドとワーカースレッドの二つだけが必要です。LongRunningをつけてもつけなくても結局残りのスレッドプールはまるまる無駄な資源となりますし、結局スレッド間通信はTaskだろうがThreadだろうがやることは同じです。Taskは細かい処理をわーっと並べてwait(join)する用途には最適ですが、一つの長大な時間のかかる処理のためには無駄が多すぎます。
もちろん、書きやすいというメリット(Task.Run(()=>{});と書けるのはとても楽ですよね)もあるし、高々無駄なスレッドプールがいくつか生成される程度の無駄なら無視できる、ということを理解したうえであえて使うというならわかります。
しかし、無条件に利用するとなるとこれは考え物です。
以前、Taskによるasync/awaitはスレッド生成のコストがかからないとか意味不明な発言を読んだことがあります。
最初はスレッドプールを使いまわすという意味で言っているのかと思ったのですが、どうも本気でスレッドを起こさないと思っているようでした。もしそうなら、E*菌とかス*ラー電磁波とか並みいるオカルト諸先輩方もびっくりなさることとおもいます。
折角ある脳みそですから使ったほうがいいと思います。多分。