1. Explain each of the five algorithms in Section 2 in your own words, and give a small example of the workings of each.
2. Describe and analyze a procedure for finding the median (or any other rank) out of M keys in a linear number of steps by dividing the keys into blocks of size 7 instead of 5. How many comparisons do you need to sort a block of size 7?
What bound can you find of the form cM using this approach?
( how small can you get c to be?)
3. Set up a Batcher's algorithm spreadsheet for 32 keys, so that if you input 32 numbers on the left, they come out sorted on the right.
How many comparisons do you need?
How many do you need in worst case for merge sorting and 32 keys?
Give similar rough results for 2^k keys.