|< < 37 > >|

External Sorting

Merge the runs (cont.)

• If ceil(N/B) < B−1, then we can merge everything in one merge.

• Otherwise:

  • Merge B−1 runs, with B pages each.

  • This produces runs of length B(B−1). (Longer runs, fewer of them.)

  • Keep generating longer runs until the number of runs < B−1.

  • Then a single sorted run can be generated: the sorted file.

|< < 37 > >|