Given n values to be sorted. 1. Write the general k-way SORT-MERGE algorithm kWayMergeSort(n, k, m)...

 

Transcribed Image Text:

Given n values to be sorted. 1. Write the general k-way SORT-MERGE algorithm kWayMergeSort(n, k, m) so that it splits the input into k 2 partitions in each round down until each partition contains m < < n values and use insertion sort to sort each of the smallest parti- tions of size m. (Hint: take floor or ceiling of division. And use one array of size n to keep all partitions, but you must be careful how to handle the boundaries of each partition). Your algorithm should then merge k> 2 partitions in each round up until it gets back the n values together sorted. Assume n> (2 x k x m). 2. Show that your algorithm is loop invariant. 3. Implement your algorithm using any programming language of your choice. Test your program on your own data. Use three data sets in your testing, one small n = (4x kx m), one mid-size n> (100 x kx m) and one large n> (10000 x kx m), where k = 4 and m= 10 for the testing. 4. Capture and compare the actual computer run time of your program for each of the three datasets. Given n values to be sorted. 1. Write the general k-way SORT-MERGE algorithm kWayMergeSort(n, k, m) so that it splits the input into k 2 partitions in each round down until each partition contains m < < n values and use insertion sort to sort each of the smallest parti- tions of size m. (Hint: take floor or ceiling of division. And use one array of size n to keep all partitions, but you must be careful how to handle the boundaries of each partition). Your algorithm should then merge k> 2 partitions in each round up until it gets back the n values together sorted. Assume n> (2 x k x m). 2. Show that your algorithm is loop invariant. 3. Implement your algorithm using any programming language of your choice. Test your program on your own data. Use three data sets in your testing, one small n = (4x kx m), one mid-size n> (100 x kx m) and one large n> (10000 x kx m), where k = 4 and m= 10 for the testing. 4. Capture and compare the actual computer run time of your program for each of the three datasets.