You are given k sorted arrays of keys A1 . . . Ak. Each key is a float number. T

Question

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 computer’s 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.

Explanation / Answer

(a)

Mergesort and heapsort both have O(log(n)) complexity.However, It is suggested that merge sort will be best suited in this case as it is stable(It doesn't change the order of equal keys as in input arrays) than heapsort(which is also in O(log(n) family).However, merge sort requires extra space to store merged arrays.It is mentioned in the question that it is assumed that there is no constraint on memory availability, so merge sort is best-suited sorting algorithm here.

Mergesort works like this:

(b)

As heap sort is in-place algorithm so it doesn't require extra space for arrays and thus minimizes further read and write operation as the assumption is written is slower than the read operation.

Heap sort works as follows:

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.