CODEWITHSUNDEEP
algorithmmergeanalysis
user355002
user355002

Reputation: 881

merge k lists with o(nlogk)

Is the running time of the Merge algorithm O(n log k)?

algorithm MakingAHalf(List_Of_Lists)
    if List_Of_Lists.size() = 1
        return the only list in List_Of_Lists
    else
        split List_Of_Lists into two halfs (First_Half and Second_Half)
    MakingAHalf(First_Half)
    MakingAHalf(Second_Half)
    Merge(First_Half, Second_Half, Min_Heap)

algorithm Merge(First_Half, Second_Half, Min_Heap)   //T(n) = O(n log k)?
    while First_Half  is not empty and First_Second is not empty do
        if First_Half.first().element() < Second_Half.first().element() then
            Insert(Min_Heap, First_Half.remove(First_Half.first()))
        else
            Insert(Min_Heap, Second_Half.remove(Second_Half.first())  
    while First_Half is not empty do
        Insert(Min_Heap, First_Half.remove(First_Half.first()) 
    while Second_Half is not empty do
        Insert(Min_Heap, Second_Half.remove(Second_Half.first())

algorithm Insert(A, key)
    A[n+1] <-- key
    while (i > 1) and (A[i] > A[[i/2]]) do
        swap A[i] and A[[i/2]]
        i <-- i - 1

Upvotes: 0

Views: 1246

Answers (2)

Tianyi Liang
Tianyi Liang

Reputation: 260

Merge is O(log N), MergeSort is O(NlogN). HeapSort is another algorithm.

Upvotes: 0

Aryabhatta
Aryabhatta

Reputation:

Looking at your code, it seems like you are very confused about what minHeaps are. The code you have is quite wrong and talking about it's time complexity in doing merge sort borders on being meaningless.

Your Merge method is doing nothing to merge two lists, all it is doing is inserting elements into MinHeap and that too in sorted order!, which seems completely pointless.

If you are using MinHeap as a heap accesible to all calls and later read from it, then it is O(n logn) as you are inserting n items into the heap and you don't really need all those recursive calls, just insert them one by one!

Since this seems like homework, I will only give you a hint: At any time, the heap should not have more than k elements in it.

Upvotes: 1

Related Questions