|< < 38 > >|

External Sorting

Merge the runs

Applied to our example

• N = 14

• B = 3

• There are ceil(N/B) = 5 runs.

• For merging, we have 3 pages: 2 for input, 1 for output.

• I.e., 2-way merges.

|< < 38 > >|