Problem
On MergeSort:
(a) Explain, using an example, why the Merge Procedure in MergeSort cannot run in-place.
(b) Although MergeSort has a Divide and Conquer formulation, the actual recursive pseudo-code can be unrolled, so that it can be re-expressed iteratively. Re-write MergeSort using an iterative algorithm, to sort a list of n elements.
(c) State (but do not prove) a loop invariant for Iterative MergeSort.
(d) Show that the run-time of Iterative MergeSort is still O(n log n).
(e) In what sense is the variant in (b) more efficient?