Question
Code merge sort where you replace the procedure MERGE(A; p; q; r) on page 34 by the procedure HEAPSORT(A) on page 160. In other words, you will use heapsort to combine the solutions to sub-problems in merge sort. The base case for this algorithm will be when the size of the sub-problems are smaller or equal to 4 in which case you will use heapsort to sort the integers of the sub-problems. All the sorting is done in a single array, you should not use intermediate arrays. You need to do the following: (a) Your program should be able to open and read a le named In- putArray that contains a single line of n integers where n is a power 2 less than 1000. (b) Your program will output on the standard output one sorted array (on a single line, where each number is separated by a space). (c) On your solution sheet, i. Write the pseudo-code of your algorithm, be careful about your array indexes. ii. Write the recurrence relation corresponding to the pseudo- code, don't forget the cost of the base case. iii. Write the solution of your recurrence, showing how you have solved the recurrence.
Explanation / Answer
#include #include using namespace std; void Merge(int *ar1,int n,int *ar2,int m) { int r=m+n,ar3[r],z,i,j; i=j=z=0; while(i