Question

Professor Strongmind has developed a hardware priority queue device for his computer. This de- vice can store up to p records, each containing a key and a small amount of satellite data (such as a pointer). With this device, INSERT and EXTRACT-MIN operations on the priority queue can be performed in O(1) worst-case time each, as long as the records are stored in the device. Your task is to develop a sorting algorithm using the device. Suppose there are n records to be sorted, origi- nally residing in main memory. (The hardware device can be viewed as a special-purpose cache.) Clearly, if n < p, you can sort in O(n) worst-case time, by inserting the n records to the hardware priority queue and then repeatedly extracting the minimum. Now suppose n > p. Design and analyze a divide-and-conquer sorting algorithm using the hardware priority queue that runs in O(n log, n) worst-case time. Note that p is a given parameter and is not considered as a constant. (Hint: Modify merge sort, and also use the hardware priority queue.)

Answer 1

Algorithm sort (start, end) int mid[p-17; if (start < end) for (i = 0; i <(p-1), itt) { mid tij = (2+1) + (1/2); p-way, merge (start, end, mid, end-start); p-way merge function call will merge elements from start to end which are divided into p parts. In such a way that at a time men- elements from all p-parts are push into priority queue and min of pushed elements is replaced on that sorted. Therefore, for merging no elements will time in required O(n) ~ n. Now, T(n) = PT(A) tn = p {pit (11/2) + 2 } tn - p²T(A) + 20 - :p2 px 7 (1/3) + 2 } + 2n - yoy p3. T() + 31 a pk T(7) tkn net = 0( 1) = 1 = [ka log ?. . T(n) = n + mx log in - T(n) ~ On Login)