Module 7: Sorting

• Module Home
• Activity
• Lab
• Extensions

Lab

• 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.

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.
• Implement the methods with FIXME as described in the comments.
• You MUST write out your pseudocode for each FIXME before you write your Java code. No credit will be given for Java code without pseudocode!
• 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).
• Check the Grading Rubric for this lab.

K-way merge sort

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.

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.

  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

• You are given 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.

Having trouble?

How to submit your work

• The unit tests are random. Run them several times so that you know you code is functional.
• Make sure all of your work is committed and pushed in your repository.
  If you get a rejected message when pushing, pull and then try pushing again.
• If you do not push your code, we cannot grade it; your lab will be considered late!
• Your work will be graded as of the due date for this assignment.

Submitting your work (read carefully)

• You must commit all of your work to your repository and push it. It's best to do this from the top-most level of your repository, which bears your wustl key.