Problem:
k-way-Merge Sort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, then merge the 4th given array with the merged version of the first three arrays, and so on until you merge in the final (kth) input array. What is the running time taken by this successive merging algorithm, as a function of k and n? (Optional: can you think of a faster way to do the k-way merge procedure ?)
Solution:
For simplicity, we say the time required for a merge is simply equal to the sum of the list lengths.
So for the first merge, we have $ T(1) = n + n $
For the second merge, we have $ T(2) = n + 2n $.
...
The overall sum of these numbers would be $ \frac{n\sum\limits_{i = 2}^{k}}{k} = \frac{n(k(k+1) - 1)} = O(nk^2) $.
The last equality in some sense is trivial. In some sense, it is totally non-obvious what do we actually mean when we put two variables in the Big Oh notation. Let's clarify what is going on there.
The faster way to do k-way-Merge sort is to use a priority queue, see the implementation at my other blog: LeetCode OJ - Merge k Sorted Lists
k-way-Merge Sort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, then merge the 4th given array with the merged version of the first three arrays, and so on until you merge in the final (kth) input array. What is the running time taken by this successive merging algorithm, as a function of k and n? (Optional: can you think of a faster way to do the k-way merge procedure ?)
Solution:
For simplicity, we say the time required for a merge is simply equal to the sum of the list lengths.
So for the first merge, we have $ T(1) = n + n $
For the second merge, we have $ T(2) = n + 2n $.
...
The overall sum of these numbers would be $ \frac{n\sum\limits_{i = 2}^{k}}{k} = \frac{n(k(k+1) - 1)} = O(nk^2) $.
The last equality in some sense is trivial. In some sense, it is totally non-obvious what do we actually mean when we put two variables in the Big Oh notation. Let's clarify what is going on there.
The faster way to do k-way-Merge sort is to use a priority queue, see the implementation at my other blog: LeetCode OJ - Merge k Sorted Lists
No comments:
Post a Comment