First sort, then merge, like a Merge Sort.
IO:
Sort in input buffer, write it to output buffer. When output buffer is full, write it to disk.

  • Optimizations:
    • Rather than just sorting individual pages, let’s load B pages and sort them all at once into a single sorted run.
    • Merge more than 2 sorted runs together at a time.
      image.png