K-way Mergesort with Binary Heap Priority Queue

Task

This homework, on the other hand, requires you to perform an empirical analysis of algorithmic alternatives. Furthermore this homework is also intended to give you greater familiarity with recursion (divide-and-conquer), the use of heaps, and finally, more practice with debugging and constructing good test cases.

If you are not fully familiar with mergesort yet, read section 2.3 in the textbook first!

Mergesort is a good algorithm. It runs in O(nlogn) time in the worst case. But let’s say we want to use it in a real application, which means we want to make it run as fast as possible. One idea for how to improve the performance of mergesort is to break the recursion into k parts instead of just 2. The recursion tree would be shallower, and so maybe the algorithm would run faster. This version of mergesort is called k-way mergesort.

Imagine k to be a medium-sized number (imagine it to be 20). If we just take the regular mergesort algorithm and modify it so that it breaks up the array into 20 equal parts and then merges the 20 sorted subarrays, we discover that it takes 19 comparisons to determine the minimum when we do the merge. Then we have to do 19 more comparisons to find the next minimum. It would take O(kn) time to do a merge and so the algorithm would run in O(knlog_k n) total time. Very slow.

An improvement is to use a Priority Queue ADT (implemented as a binary heap) to make that merge process require less work. We put each of the 20 numbers in a binary heap, and when we need a number to output, we do a deleteMin operation, put that number in the output array, and then insert the next number from the subarray (if there is one) into the heap. So, to do the merge, it would take O(nlogk) time. If you work through the analysis, you will discover that k-way mergesort takes O(nlogn) time. But that still leaves the question: which value of k leads to the fastest implementation of k-way mergesort?

To find out, you will code k-way mergesort and run timing experiments to decide what value of k is best. You will need to implement the merge method using a binary heap. After you have implemented a correct version of k-way mergesort, you will then run experiments on different values of k and different input sizes.

Learning Objectives

The binary heap code, and the operations that you need to use it as a priority queue, such as insert and deleteMin, are provided for you. You do not need to make modifications to the BinaryHeap class, just use it as it is. The overall code for mergesort and doing the timings are also provided for you. You only need to adapt the merge method in Sort.java so that it does a k-way merge using a binary heap.

For the experiments, choose values of k = 2,3,5,10,20,50 and input sizes n = 200,000, 400,000, 800,000, 1,600,000, and 3,200,000. Run the algorithm three times for each size and average the results. In other words, you will need to run the algorithm 90 times in total. For each value of k, plot your results on a graph (x-axis is the input size; y-axis is the time in milliseconds it takes to sort), connecting the dots for each value of k. Make sure that the x-axis and y-axis values are drawn to scale. Create a single figure (graph) with all of your results, rather than making individual figures for every value of k.

The java code to start with is available on the course Canvas webpage: Sort.java, Binary Heap java Mergesort Heap Node.java, Empty Heap Exception java.

Located within the merge method (line 76):

Divide the array into k subarrays and do a k-way merge

This comment means the following. The subrange from low to high in the data array contains k subarrays. Each of these k subarrays is sorted. The else block is supposed to extract these k subarrays from data and do a k-way merge of them, sorting them in the process.

Electronically turn in your modified Sort.java file on the course Canvas webpage. You should not have to modify the mergesort method. You should only modify the merge method and any code to help you do the timings or test for correctness.

Submit a report (hard copy) in class. This report should contain:

A hard copy of your code.

A graph that indicates how much time is spent for different values of k and different sizes of input (see above).

An analysis of the results: how do you explain the experimental results? What can you conclude about k-way mergesort?

A description of (at most) one page on how you approached the problem, what troubles you had, and what you learned.

This assignment will be graded on a scale of 30 points (15 points for the code, 10 points for the graphs and the result analysis, 5 points for the description of how you approached the problem).

The minimal requirement is that your code is correct, i.e. that your implementation correctly sorts inputs for different values of n and k. If your solution does not satisfy this basic requirement, it will become very hard to give you credit for the other parts such as the graph and the result analysis too.

Another requirement is that your code implements k-way mergesort and not another sorting algorithm like heapsort. Note that you are expected to use a heap of size k to facilitate a merge of k sorted subarrays; this is different from putting all elements of these k sorted subarrays on a heap simultaneously and extracting them one by one. In particular, the heap in your implementation should not contain more than k elements at once.

Test your code on small values of k and input size n. See how the heap changes. Verify that the output to the merge method is correct. Does your code work correctly when one or more of your subarrays has no more elements?