Tow Way External Merge Sort

Similar to merge sort, but we perform sorting on pages.

Divide and Conquer idea

• Divide: Take Page as the sorting unit.
• Conquer: Merge tow sorted pagespages]]

• The I/O cost $=2N\times passes$ (for every pass we need read and write one page)
  • $passes=\lceil lo{g}_{2}N\rceil +1$
  • So total cost $=2N(\lceil lo{g}_{2}N\rceil +1)$