External Sorting

1. Is there any advantage to using natural selection over replacement selection when the input keys are already in sorted order? What about if the keys are in reverse sorted order? Explain.

2. You wish to generate sorted partitions using the three methods discussed in class. If your input file consists of 100 records, explain how many partitions will be generated, and how long each will be, if you used (i) internal sorting, (ii) replacement selection, and (iii) natural selection, for the following three cases:
   • Input file is unsorted (random ordering)
   • Input file is initially sorted
   • Input file is initially sorted in reverse order

3. Suppose you can have three files open at a time. Given a series of 10 partitions, how you would distribute them across the input files for a polyphase merge, that is, how many partitions would you place in each file? Indicate any dummy partitions you use as well. Show all your work.

4. In the polyphase merge algorithm for F = 4, where F is the total number of open files, we know that if the distribution of partitions at step i is:

   File 1	File 2	File 3	File 4
   a >=	b >=	c >=	0

   then at step i-1, the distribution must be:

   File 1	File 2	File 3	File 4
   0	a+b	a+c	a

   Prove that for F=4, polyphase merge requires the total number of partitions (possibly including dummy partitions) to be a member of the Fibonacci series of order 3.