|< < 6 > >|

External Sorting

Analysis

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

• Last run length = B(B-1)^k-1.

• Obviously, last run length is N.

• So solve B(B-1)^k-1 = N for k.

• B(B-1)^k-1 = N/B

• (k-1) log(B-1) = log(N/B)

• k = 1 + log(N/B) / log(B-1)

• k = 1 + log_B-1(N/B)

|< < 6 > >|