Loading article…
内部ソートとは、コンピュータのメインメモリ内で完全に実行されるデータソート処理のことです。これは、ソート対象のデータがハードディスクなどのメインメモリにすべて格納できるほど小さい場合に可能です。この低速なメディアとの間でデータの読み書きを行うと、ソート処理が著しく遅くなる可能性があります。この問題は、さまざまなソートアルゴリズムに影響を与えます。
一般的な内部ソートアルゴリズムには以下のようなものがあります。
バブルソートを考えてみましょう。これは、隣接するレコードを交換して正しい順序に並べるアルゴリズムで、レコードがデータ空間を上下に「泡立つ」ように見えます。これをチャンク単位で行う必要がある場合、チャンク 1 のすべてのレコードをソートしたら、チャンク 2 に進みますが、チャンク 1 の一部のレコードがチャンク 2 を「泡立つ」必要があり、その逆も同様です (つまり、チャンク 2 にはチャンク 1 に属するレコードがあり、チャンク 1 にはチャンク 2 以降のチャンクに属するレコードがあります)。レコードがチャンク間の境界を越えるたびに、チャンクが何度もディスクに読み書きされるため、パフォーマンスが著しく低下します。データをすべて 1 つの大きなチャンクとしてメモリに保持できれば、このパフォーマンス低下は回避できます。
一方、外部ソートをより効率的に処理できるアルゴリズムも存在します。マージソートは、データをチャンクに分割し、別のアルゴリズム（バブルソートやクイックソートなど）で各チャンクをソートした後、チャンクを2つずつ再結合して、各再結合チャンクが正しい順序になるようにします。このアプローチは、ディスクからのデータチャンクの読み書き回数を最小限に抑えるため、外部ソートの一般的な手法となっています。