You are given k sorted arrays of keys A1 . . . Ak. Each key is a float number. The total number of keys is n. Your goal it to sort all these keys in time O(n log k).

(a) Suggest a solution under the assumption that there are no constrains on memory availability nor on access time to memory, and access to each memory cell takes a constant time.

(b) Suggest a solution under the following assumptions: Each Write Operation is much slower than a read operation (as is commonly the case for Solid State Driver). However, you have access to fast memory containing O(k) words. (hint - you might need to borrow some ideas from CSC345). To elaborate, assume that your computers memory contains two major components:

i. SlowMem - a slower memory. Reading and writing from this components are slower. The input arrays are stored in SlowMem, and the final output should be writing to SlowMem. Your algorithm should keep the number of reads/writes from SlowMem to the bare minimum.

ii. FastMem - a faster memory unit. Could only contains say 10k words.