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