Understanding and solving K-Way merge sort

Question

I want to:

1. count the number of comparisons needed by k-Way merge sort to sort random permutation of numbers from 0 to N-1.

2. to count the number of data moves needed by K-Way merge sort to sort random permutation of numbers from 0 to N-1.

I understand how 2-way merge sort works correctly, and understand the code very well. My problem now is I don't know how to start. How do I convert the 2-way merge sort into K-Way so that I can solve the above problems?

I have searched the web but can't find any tutorial to explain "k-Way merge sort" very well.

I need good explanation what to do so that I can take it from there and do it myself.

Like I said I understand the 2-Way, so how do I move to the K-Way merge sort? How do I implement the K-way?

Edit

I read some post http://bchalk.com/work/view/k_way_merge_sort that BinaryHeap must be used to implement k-Way merge. Is that so or there are other ways?

How do I divide my list into K? Is there a special way of doing it?

Answer 1

When k > 2, the leading elements from each of the input streams are typically kept in a minheap structure. This makes it easy to find to the mininum of the the n-values, to pop that value off the heap, and insert a replacement value from the corresponding input stream.

A heap does O(lg2 k) comparisons for each insertion, so the total work for a k-way merge of n items is n * lg2(k).

Eventhough you asked about C# and Java, you can learn how to do it by looking at the Python standard library code for a k-way merge: http://hg.python.org/cpython/file/2.7/Lib/heapq.py#l323

To answer your other question, there is no special way to divide your list into K groups. Just take the first N/k elements in the first array, the next N/k elements into the next, etc. Sort each array and then merge them using heaps as mentioned above.