# Difference between revisions of "TADM2E 4.14"

The elementary algorithm compares the heads of each of the $k$ sorted lists to find the minimum element, puts this in the sorted list and repeats. The total time is $O(k n)$. Suppose instead that we build a heap on the head elements of each of the $k$ lists, with each element labeled as to which list it is from. The minimum element can be found and deleted in $O(\log k)$ time. Further, we can insert the new head of this list in the heap in $O(\log k)$ time. An alternate $O(n \log k)$ approach would be to merge the lists from as in mergesort, using a binary tree on $k$ leaves (one for each list). problem