|< < 36 > >|

External Sorting

Merge the runs

• We have B pages in memory.

• We need to use them for merging:

  • Use 1 page to read pages in order from each of B−1 runs.

  • Use the remaining 1 page to write output.

• There are ceil(N/B) runs.

|< < 36 > >|