[sgeisenh]

I'm curious, what kind of a solution are you looking for with that problem? The trivial solution of concatenating the lists and then using a library sort (or cobbling together quicksort) is about as good as it gets for small lists.

For large lists, the best you can do is copy the lists into an array, use a parallel n * log n array sort, then fix the pointers.

The problem doesn't seem to require any real thought. It is difficult to make optimizations because the problem isn't especially well defined and the optimal asymptotic performance is obvious the moment the word "sorted" is uttered.

[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).