CSE 247 Module 7: Sorting

Lab

You have previously studied classical merge sort, in which the following steps are recursively applied to sort a collection of values:
• If n=1 or n=0 then the collection at hand is trivially sorted.
• Otherwise, the collection of n values is divided into two subcollections, each of size n/2.
• The subcollections are recusively sorted by this algorithm.
• The two sorted subcollections of size n/2 are merged into a sorted collection of size n.
Recall that the recurrence describing the time to perform this 2-way merge sort is T(n) = 2T(n/2) + n. The solution to that recurrence is T(n) = Θ(n log n).

In this assignment, you consider a more general form of merge sort. Instead of dividing a collection of into 2 subcollections, you consider dividing them into K subcollections.

Instructions

• Pull from your upstream repo to make sure you have the latest distribution of code.
• Find and open the kwaymergesort package in the labs source folder.
• The work you do for this lab is only inside the KWayMergeSort class, in which you complete the kwaymergesort method as described in the comments of that class.
• When your code is working, it should pass the TestMergeSort unit test found in the kwaymergesort.test package.
• The MergeSortTimer class will generate the usual .csv file, and you should open that and verify that the time taken by your algorithm is Θ(n log n).

K-way merge sort

Your kwaymergesort method has the following parameters:
K
This is the way of the merge sort, and is some positive power of 2.
input
is an array of Integers, not necessarily sorted. The size of this array is the complexity parameter n.
For this assignment, you can assume n is a positive power of K.
ticker
As before, you call .tick() on this object to keep track of the operations you perform in your algorithm.

• If the input array contains just one element, then it is sorted, and can be returned as the answer. Otherwise, press on…
• The elements of the input array are distributed among K other arrays, each of size n/K.
Because K and n are both powers of two, with n≥K, each of the K arrays has the same number of elements, which is also a power of 2.
• Recursively call kwaymergesort on each of the K arrays, and keep track of the arrays returned by each call.
Each of the returned arrays is sorted, so you now have K sorted arrays.
• Your task now is to merge the K sorted arrays, each of size n/K into a single array of size n, which will be returned as the answer from this call. More detail on this is given below.

Merging K arrays into one array

Tim and Yoni, would be nice to have some pictures for this
• You are give K arrays, each of which is sorted, and you need to merge these K arrays into a single result.
• Conveniently, K is a power of 2.
• Thus, we can think about merging K sorted arrays by considering the arrays in even/odd pairs.
• Suppose these are numbered 0, 1, …K-1.
• Then the even/odd pairs are (0,1), (2, 3), …(K-2,K-1)
• Using only a 2-way merge method, we can merge the K arrays into K/2 arrays by merging each pair. Each such merge leaves its two inputs alone, and creates a new array twice the size of either input.
• (0,1) are merged to create a new array
• (2,3) are merged to create a new array
• etc.
• Because K is a power of 2, so is K/2.
• We continue this process until the last step, when we have 2 arrays left (1 pair), and we merge them in the final step.

• Make sure your code passes the tests as we originally gave them to you. It's those tests we will run to see if your code functions properly.
• Make sure you have placed ticker.tick() calls appropriately in your solution. Failure to do so will cost you points on this assignment.
• Make sure your solution's ticks behave in a manner consistent with the asymptotic complexity you should see for your solution.
• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
You can tell that your code was pushed by logging into bitbucket.org, clicking on your repository, and seeing the push in the associated log traffic.

Because of this, you have no excuse for failing to push your code. Check and make sure it was pushed so your work is counted.

Work that is not pushed will receive no credit.