Assume that each record has four bytes of data and a 4-byte key, for a total of eight bytes per record:
8-byte record
4-byte key
4-bytes of data
A 4KB block
contains 512 8-byte records
One block from input file:
512 records in 4KB.
One block from output file
after sorting: 512 sorted
records in 4KB.
Unsorted block of 512
records.
Sorted block of 512
records
Apply one pass of an internal sort
512 blocks each with
512 sorted records
One run of 256k
sorted records
Apply nine merge passes