Full External Sort

Unlike Tow Way External Merge Sortpages]] into buffer as many as possible.

Say we have $B$ buffer pages. We have optimizations compared to Tow Way External Merge Sort:

• Load $B$ pages in to buffer and sort them all at once.
• Merge $B-1$ sorted runs because we should take 1 buffer as ouput.

I/O cost:

• Number of passes: $1+\lceil lo{g}_{B-1}\lceil N/B\rceil \rceil$
• Total I/Os = (I/Os per pass) $\times$ (# of passes) = $2N(1+\lceil lo{g}_{B-1}\lceil N/B\rceil \rceil )$