Exercises

The following exercises provide you with the opportunity to practice with external-memory sorting as well as merging K sorted lists. The solutions to these exercises are found in the section .

1. Here’s a diagram depicting an example of M/B-Way Mergesort:

   

   How many I/Os take place in total?

2. How many I/Os would M/B-Way Mergesort take if we modified this scenario so that M=64 instead of M=16?

3. Say that we’re conducting the Top-Grade Merge algorithm to merge data that fits entirely within memory. Specifically, we have one million values divided among 512 lists. How many steps will our merging algorithm take?