|< < 34 > >|

External Sorting

Let's review mergesort and adapt it for external sorting:

Divide the input into subsets

• The file has N pages, 0, ..., N−1.

• Define subsets as sequences of B pages.

• Subset 0: Pages 0, ..., B−1.

• Subset 1: Pages B, ..., 2B−1.

• ...

• There are ceil(N/B) subsets.

|< < 34 > >|