CODEWITHSUNDEEP
algorithmdata-structures
infinity
infinity

Reputation: 158

Finding an algorithm for merging sorted list

The question goes as follows : There are k sorted lists of length n/k (we assume that k divides n). I need to find an algorithm that merge those lists into one list of length n with running time complexity O(k + nlogk).

I was thinking of merging the lists by couples , than merge the merged lists again by couples, and so on and I stop when I get to a one sorted list of length n.

When I calculated the time complexity of my algorithm I got O(nlogk) which is batter than the time needed.

I was wondering if my way is wrong. Thanks for helping !

Upvotes: 1

Views: 96

Answers (3)

invisal
invisal

Reputation: 11181

It is easy to see that O(nlogk) is O(k + nlogk) because k <= n as mentioned by @MattTimernans. It is easy to get O(k + nlogk) by using heap. First we build the heap of the all first element of each list which takes O(k). Then, we pop an element and push a new element back into the heap. Continuing to do it N time, we will have a sorting list by merging all the list in O(k + nlogk)

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59253

Your way is fine.

When it's given that k<=n, and k>=1, then O(n log k) = O(k + n log k). Both of these are implied by the statement that "we assume that k divides n", so your results are what they're supposed to be.

If we relax those conditions, then we have to consider the cases where k>n, and some of those k lists are empty. Then you have to worry about the time taken to merge all those empty lists, and your algorithm takes O(k + n log k) time.

Upvotes: 1

Codor
Codor

Reputation: 17605

To my understanding, it is possible to achieve a running time of

O(k^2*(n/k)) = O(kn)

by the following idea. Suppose the lists are sorted in nondecreasing order. Iterate until all lists are empty. In each iteration, use k steps to determine for which list the first element is minimum with respect to all the first elements of the lists. Remove the element from the list and append it to the result.

Upvotes: 0

Related Questions