|< < 44 > >|

External Sorting

Analysis

So the obvious question is: How many passes are required to sort N pages using a buffer of size B?

The first pass

Subsequent passes

• We are doing B−1 way merges.

• So the number of passes is log_B−1(ceil(N/B)).

Total passes

So the total number of passes is: 1 + log_B−1(ceil(N/B))

= 1 + log(ceil(N/B)) / log(B−1).

|< < 44 > >|