Understanding and resolving K-Way merge sort

Question

Am to

1) count the number of comparisons needed to sort the k-Way merge to sort an arbitrary permutation of numbers from 0 to N-1.

2)

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

I understand how 2-way merge sorting works correctly and understands the code very well. My problem now is that I don’t know where to start, and you need a little help. How to convert two-way sorting to K-Way so that I can solve the above problems.

I have some time to search on Google, but I can’t find any tutorial to help me very well understand k-Way merge sort.

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

As I said, I understand 2-Way, so how can I go on to sort the K-Way merge? How to implement a K-way.

Thanks for the help.

EDIT

** I read the post http://bchalk.com/work/view/k_way_merge_sort that BinaryHeap should be used to implement k-Way merge. Is this true or are there other ways?

** How do I divide my list by K? Is there a special way to do this?

Answer 1

When k > 2 , the leading elements from each input stream are usually stored in the minheap structure. This makes it easy to find a minimum of n-values ​​in order to get this value out of the heap and insert the replacement value from the corresponding input stream.

The heap does O(lg2 k) comparisons for each insert, so the overall job is to merge the k-way of n elements n * lg2(k) .

If you asked about C # and Java, you can learn how to do this by looking at the standard Python library code for k-way merging: 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 groups K. Just take the first N / k elements in the first array, the next N / k elements in the next, etc. Sort each array and then combine them using heaps, as described above.

Answer 2

You can always think of a k-way merger as a series of two-way mergers, i.e. perform a two-way merge with the result of the first and second and third: Merge(Merge(L1, L2), L3) , etc., It would be even faster to split it twice: Merge(Merge(L1, L2), Merge(L3, L4)) . As you can see, to sort k-way you need some kind of loop (recursion).