|< < 39 > >|

External Sorting

Merge the runs

Applied to our example

• Merge up to 2 runs at a time.

• Input: 5 runs of size ≤ 3.

• Output: 3 runs of size ≤ 6.

Not done

|< < 39 > >|