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


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 K.
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:

Merging K arrays into one array

Tim and Yoni, would be nice to have some pictures for this

Submitting your work (read carefully)

Last modified 14:14:22 CST 01 December 2016