Merging Sorted Lists using Heaps

I need help figuring out an algorithm that will merge k sorted lists into one sorted lists in O(n lg k) time where n is the number of elements in ALL the input lists. I believe we are supposed to use a Heap for k-way merging.

radix sort

Attached is a problem asking if radix sort would be appropriate. I think it would not be appropriate. Can you help give me reasons why? One of the reasons why I think radix sort is not better then the other is because radix is linear, and the other one is n log n (which I believe is faster?).

sorting an array of integers in linear time

How can I sort an array of integers in O(n) time, where different integers may have different numbers of digits, but the total number of digits over ALL the integers in the array is n? My assumption is that radix sort is somehow involved.

explanation of solution

The solution seems to be the the following, but I need a more in-depth explanation, particularly on why we should use merge sort and binary sort. Here is the problem at a high level (you can look at the attachment for more detail): Describe a (n log_2 n) time algorithm that, given a set S of n real numbers and another real number x, determines whether or not there exist two elements in S whose sum is exactly x. Solution: Sort the array using an algorithm of order O(n log n) (You can use mergesort but you cannot use quicksort) Then for every element y in the array binary search the sorted array for x - y O(n log n) + O(n log n) = O(n log n)

Min heap problem: merge k sorted lists into one sorted list in O(n lg k) time

Recall this problem -- define an algorithm that will merge k sorted lists into one sorted lists in O(n lg k) time where n is the number of elements in ALL the input lists... My question is why do we define a comparison that states the following: "We shall also need to define comparison with empty lists, and so we define it taking that any non-empty list is smaller than the empty list." when we already established this: "Now let us take our k sorted lists (of arbitrary lengths) and define the comparison between the lists by their smallest elements."