While HeapSort is more amenable than MergeSort to an in-place implementation, MergeSort has its own advantages. For this problem, suppose you want to perform MergeSort on a really huge array A. The array is so big that it doesnt fit in your computers memory and has to be stored in the cloud.

More specifically, assume that our computer has enough memory to hold 3b elements, for some constant b, but A has size n much greater than b. We can call read(X, i, B) to read a chunk of b elements from an array X (in the cloud) starting at index i into a local array B. Similarly, we can call write(C, X, i) to write a chunk of b elements stored in local array C to a cloud array X starting at index i.

Heres a proposed (incomplete!) implementation of the merge operation that merges cloud arrays X andY into cloud array Z. The code uses local arrays A, B, and C, each of size b, to cache X, Y , and Z. For simplicity, we assume that the input arrays X and Y have sizes a multiple of b, and that reading past the end of either X or Y returns values as in the studio. mod is the integer modulo operator (% in Java).

10. What is the total number of cloud read and write operations performed by MergeSort to sort an array A of size n stored in the cloud? Give an asymptotic answer in terms of n, the number of elements inA, and b, the chunk size. How does this cost compare to the asymptotic cost of merge-sorting an array of size n held entirely in your computers memory?

11. Why might MergeSort be preferable to HeapSort in the cloud sorting model, where the cost is based on the number of chunk reads and writes?

MERGEX, Y, Z) k0 READ(X, 0, A) READ(Y, 0, B) while A[i mod b] oo or B[j mod b] x do u - Ali mod b Clk mod b- min(u, v) FOO else BAR if k mod b 0 WRITE(C, Z, k -b) MERGEX, Y, Z) k0 READ(X, 0, A) READ(Y, 0, B) while A[i mod b] oo or B[j mod b] x do u - Ali mod b Clk mod b- min(u, v) FOO else BAR if k mod b 0 WRITE(C, Z, k -b)