Advantage of k-way merge external sorting

Me and my roomie had an interesting discussion on external sorting. We were trying to find the advantages of merging the records in usual order and in merging the records in a k-way order. After a long discussion, we were able to appreciate the k-way merge.

We tried comparing the 2 ways of performing external sorting. And the advantages of k-way merging is not the complexity of the algorithm but in reducing the disk I/Os. (This was covered nicely in my graduate course of advanced data structures but I have forgot about its significance.)

For simplicity lets assume that total number of records to sort (n) = 32.

The memory capacity (m) in records = 8

Records in a run ( a run is a group of records that can be sorted in memory) = 4

Number of runs (r) = 32/4 = 8

Each run has 4 records and there are 8 runs (R1, R2.. R8)

We have an 8- record memory and 1 record output buffer

Lets try to calculate the number of I/Os in usual sorting (2 way merging)

1) 4 records are retrieved from R1 and 4 records are retrieved from R2 and pushed into memory.

8 records are merged and written back to the disk. The number of I/Os for this step is 16 (8 disk read and 8 disk writes)

Perform merging for pairs (R3, R4 ) , (R5, R6) and (R7, R8). Since the number of I/O's required for merging a pair is 16 I/Os . Merging 4 pairs takes 64 I/Os.

Merging (R1, R2) yields Ra , (R3, R4) yields Rb , (R5, R6) yields Rc and (R7, R8) yields Rd. Ra to Rd contains 8 records individually.

2) Next merge Ra and Rb into bigger run Rx which contains 16 records. The number of disk I/Os is 32 (16 disk reads for retrieving Ra , Rb and 16 disk writes for writing Ra and Rb back to disk)

Similarly merging Rc and Rd yields Ry which also contains 16 records with 32 disk I/Os.

Total number of disk I/Os in this step is 64 disk I/Os.

3) Next merge Rx and Ry. Both Rx and Ry contains 32 records each and merging them produces 64 disk I/Os (32 disk reads to read from Rx and Ry and 32 disk writes to write the sorted records back to disk.)

So total number of I/Os in this step is 64

Total number of disk I/Os in all the 3 steps = 3 * 64 = 192 disk I/Os.

The number of disk I/Os seems directly proportional to the number of phases in merging. Since we merged 8 runs in 2 way merging , we have 3 merging phases to get the output records. (lg 8 = 3)


Lets try merging using k-way merge.

Try using 8-way merging technique. So we have a single merging phase to get the output record.

1) Since m = 8 and r =8, get single record from each Runs (R1.. R8). This 8 records can be merged using a loser tree or a Priority Queue (not concerned about complexity now). To retrieve these 8 input records , 8 disk reads are needed.

After retrieving m records, 8 way merge is performed and the output is written directly to the output buffer.

After 8 disk reads are performed and merged, a record is written back to output buffer. This causes an empty record buffer since a record is written back to the output buffer. Another disk read is performed to get record from the buffer and fill the empty buffer.

After 16 disk reads and 8 way merging performed on those records, 8 records are written back to disk.

After 24 disk reads and 8 way merging performed on those records, 16 records are written back to disk.

So after 32 disk reads with 8 way merging performed on those records, 32 records are written back to disk.
( In the last phase of merging, after all 32 records are read, no disks are performed. )

The total number of I/Os required is only 64 disk I/Os in an 8-way merging technique.

Lets assume each I/O takes 10 ms. The usual technique would take 192 * 10 ms = 1.92 seconds

The k-way merge technique would take 64 * 10ms = 640 ms

The 8-way merging technique is more efficient than the 2-way merging scheme. Besides it generates the output record while overlapping with the merging phase.

Assume the scenario where output records are needed as they are sorted.

1) After 8 * 10 disk reads and 1 disk I/Os to write the sorted record to the disk, the first sorted record is available after 90 of the merging phase in the disk. [ not taking into account the cpu time to perform 8-way merge ].

2) But in the 2-phase merging, it would take 1370 ms to write the first sorted record to the disk. (The first 2 phases would take 1280 seconds. To retrieve 8 records would take 80 ms. neglecting cpu merge time. Takes another 10 ms to write the sorted record back to disk, so a total of 1370ms.)

As you could see, the 8-way merging provides the sorted record asap compared to the 2-phase merging which might be the scenario in real time processing ( correct me if i am wrong.)

How k-way merge reduces the I/O time ?

1) It does this by overlapping the computation and in writing the records to the output buffer asap.

2) Since the number of disk I/Os is directly proportional to the number of phases, it reduces the number of merging phases by merging run records in a single phase thereby significantly reducing the disk I/Os.

So a k-way merge seems to be more efficient than a usual 2 way merge. Implementation of k-way merge is more complex since it requires finding free buffers and using loser trees.

Please let me know your comments whether our assumptions are valid or we have missed something or specified something wrong. Will be very glad to hear suggestions and comments about our understanding of k-way merge.