2-Way External Merge Sort

Pass #0

• Read every B pages of the table into memory

• Sort pages into runs and write them back to disk

Pass #1,2,3,..

• Recursively merges pairs of runs into runs twice as long.

• Uses three buffer pages (2 for input pages, 1 for output).