私は外部ソーティングが何をするのか、それが何のためにあるのかを理解しています。それでも、極端なケースをマージすることについて頭に浮かぶ問題があります。
外部ソーティング 最初の答えは、外部ソーティングのマージがどのように機能するかを説明しています。しかし、もし：
10ユニットのメモリサイズがあり、50ユニットのファイルをソートするとします。
まず、ファイルを5つの実行（それぞれ10ユニット）にスライスし、個別に並べ替えます
次に、4方向マージでそれらをマージする必要があります
および10/4=2.5〜2; 各実行から2ユニット（チャンク）を取得し、それらをメモリに入れて、マージを開始します。
次に、実際の質問は次のとおりです。（想定）3回目の実行の2番目と3番目のチャンクが
他の実行の最初のチャンクよりも小さい要素？マージプロセスは成功しますか？
私が理解していることについて間違いがある場合は、どんな説明も役に立ちます。
さて、どのファイルにも小さい/大きい要素が含まれていても問題はありません。外部ソートプロセスの例を次に示します。
初期データ：
data = [2, 5, 3, 7, 1, 6, 4, 8, 9]
メモリが3ユニットしかないことを考えると、次のシャードと並べ替えの結果が得られます。
d1 = [2, 5, 3] -> sorting -> d1 = [2, 3, 5]
d2 = [7, 1, 6] -> sorting -> d2 = [1, 6, 7]
d3 = [4, 8, 9] -> sorting -> d3 = [4, 8, 9]
使用可能なユニットが3つあるので、3つのシャードから同時に読み取ることができます。つまり、次のようになります。
d = [], d1 = [2, 3, 5], d2 = [1, 6, 7], d3 = [4, 8, 9] -> min(d1, d2, d3) = 1
d = [1], d1 = [2, 3, 5], d2 = [6, 7], d3 = [4, 8, 9] -> min(d1, d2, d3) = 2
d = [1, 2], d1 = [3, 5], d2 = [6, 7], d3 = [4, 8, 9] -> min(d1, d2, d3) = 3
d = [1, 2, 3], d1 = [5], d2 = [6, 7], d3 = [4, 8, 9] -> min(d1, d2, d3) = 4
d = [1, 2, 3, 4], d1 = [5], d2 = [6, 7], d3 = [8, 9] -> min(d1, d2, d3) = 5
d = [1, 2, 3, 4, 5], d1 = [], d2 = [6, 7], d3 = [8, 9] -> min(d1, d2, d3) = 6
d = [1, 2, 3, 4, 5, 6], d1 = [], d2 = [7], d3 = [8, 9] -> min(d1, d2, d3) = 7
d = [1, 2, 3, 4, 5, 6, 7], d1 = [], d2 = [], d3 = [8, 9] -> min(d1, d2, d3) = 8
d = [1, 2, 3, 4, 5, 6, 7, 8], d1 = [], d2 = [], d3 = [9] -> min(d1, d2, d3) = 9
d = [1, 2, 3, 4, 5, 6, 7, 8, 9], d1 = [], d2 = [], d3 = [] -> []
懸念されるのは、各ファイルから少なくとも1つの要素を読み取れないようにするのに十分な制限がある場合、または単に特定のファイルからより多くの要素を読み取って、別のファイルを読み取ることを決定した場合でもです。
これは上記のプロセスと同じですが、たとえば2つのファイルを読み取り、それらの間のデータをマージした後、3番目のファイルと最後に生成されたファイルから読み取る必要があるという点が異なります。ファイル1と2のマージ。
3番目のファイルと最後に生成されたファイルの両方が確実にソートされているため、両方のファイルのデータを順番にスキャンして、エントリを一意の結果にマージすることができます。