[gabbo]

You can do better by taking advantage of the fact that the lists are already sorted. O(n1 + n2) time, where n1 and n2 are the sizes of the original lists and O(n1 + n2) space for the output.

The "trick" is to iteratively merge your two lists: at each step you select the smallest of the two items you're at in both lists then move forward on the list whose item you picked.

An extension to this problem (I've asked, and been asked, many variations of this) is to merge K sorted lists of N items each. The naive solution is to merge them all together and sort but you can do better if you extend the algorithm above from 2 lists to K and choose a helpful intermediate data structure to optimize the "select the smallest of the K items" operation. AFAIK, all-up the best you can do then is O(NKlog[K]).

EDIT: Re-read the question, realized I read "unsorted" as "sorted" - not sure what you can do to merge two unsorted lists in better than O(Nlog[N]) time beyond non-comparison-based sorts where you make assumptions about the range or distribution of your input (radix/counting/bucket sorts).

[sgeisenh]

Yeah, when the lists are sorted, you need the intuition that you can merge two sorted lists in less than n * log n time. Like you say, the best you can do for merging several sorted lists is (sum of lengths) * log(# of lists).