CSE 247 Module 7: Sorting
You have previously studied classical
merge sort, in which the following steps are recursively
applied to sort a collection of values:
Recall that the recurrence describing the time to perform this 2-way merge
T(n) = 2T(n/2) + n.
The solution to that recurrence is
T(n) = Θ(n log n).
- If n=1 or n=0 then the collection at hand
is trivially sorted.
- Otherwise, the collection of n values is divided into two
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.
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.
- Pull from your upstream repo to make sure you have the latest distribution
- 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:
- This is the way of the merge sort, and is some positive
power of 2.
- 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
- As before, you call .tick() on this object to keep track
of the operations you perform in your algorithm.
To receive full credit, your solution must perform the following steps:
- 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.
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
- 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
- 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.
Submitting your work (read carefully)
- 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.
Last modified 14:54:21 CDT 31 October 2016