Menu
I want to:
count the number of comparisons needed by k-Way merge sort to sort random permutation of numbers from 0 to N-1.
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?
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?
902
In computer science, k-way merge algorithms or multiway merges are a specific type of sequence merge algorithms that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two.
Algorithm for Merge Sort Step 1: Find the middle index of the array. Step 2: Divide the array from the middle. Step 4: Call merge sort for the second half of the array. Step 5: Merge the two sorted halves into a single sorted array.
Step 1 − if it is only one element in the list it is already sorted, return. Step 2 − divide the list recursively into two halves until it can no more be divided. Step 3 − merge the smaller lists into new list in sorted order.
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.
60
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
