merge k lists with o(nlogk)

Question

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

• k is the number of lists.
• n is the total number of elements in all of the lists (n = n₁ + n₂ + ... + n_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

Answer 1

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.