1. When we talked about insertion sort, we found that it requires only n comparisons and 0 exchanges when the input is sorted. Does this violate the lower bound proof?

a. Yes - no sorting algorithm can ever do better than nlogn comparisons.

b. No - a sorted input is a special case, while the lower bound proof applies to all inputs.

c. No - the lower bound proof only applies to mergesort or other merging sorting algorithms.

d. Yes - this means that some inputs will become unsorted.

2. If you need to sort a large dataset on a system with limited memory would it be safe to use mergesort? Explain.

a. No - mergesort requires an auxiliary array to do the merging step.

b. No - mergesort requires a linear number of recursive calls to be made.

c. Yes - mergesort has a cool name so it's guaranteed to run fast.

d.Yes - mergesort has proven optimal performance.