///////
//
// Student: Russell Lowke
//     T.F: Francis Crick
// Unit Seven, pencil-and-paper - question 5 [worth 2pts],  7/30/2002
//
//  A file of integers contains 44 runs
//  each run starts with a number less than 20 and ends with a number > 50


a) After the distribution phase of Fibonacci merge, how many real runs and
   how many dummy runs will be in each file?
   
   ... working ...
   Fib. = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144}
   A: (1) (2) (3) (5) (8) (13) (21) (34)
   B: (1) (1) (2) (3) (5) ( 8) (13) (21)
   
   There will be:
   
   A: 31 real + 3 dummy = 34 runs total
   B: 13 real + 8 dummy = 21 runs total


b) How many merging passes will be required before the file is sorted?
   Make a table showing the number of runs (real and dummy) on files 0, 1, and 2
   after each merging pass.
   
   TABLE:
   
   distribution
   0F:
   1A: 31 real + 3 dummy
   2B: 13 real + 8 dummy
   
   1st merging pass
   0F: 21 real
   1A: 10 real + 3 dummy
   2B:
   
   2nd merging pass
   0F: 8 real
   1A: 
   2B: 13 real
   
   3rd merging pass
   0F: 
   1A: 8 real
   2B: 5 real
   
   4th merging pass
   0F: 5 real
   1A: 3 real
   2B:
   
   5th merging pass
   0F: 2 real
   1A: 
   2B: 3 real
   
   6th merging pass
   0F: 
   1A: 2 real
   2B: 1 real
   
   7th merging pass
   0F: 1 real
   1A: 1 real
   2B: 
   
   8th and last merging pass
   0F: 
   1A: 
   2B: 1 real
   
   There will be eight merging passes before the file is sorted.