# 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).

![](https://2548495579-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FTsnKOX7xLvOtvOXY9MlI%2Fuploads%2Fl1m7vAs7X4yz5z44AMWm%2Fimage.png?alt=media\&token=96884651-3d29-4972-9ba2-1cf5bf4425f1)

![](https://2548495579-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FTsnKOX7xLvOtvOXY9MlI%2Fuploads%2FV5ResqyzlNp72iluBOnc%2Fimage.png?alt=media\&token=520a2d91-d8fd-449e-aa5e-f59ee21698dd)