Divide and conquer algorithm to sort nk items in n lists that runs in O(nk*logn) time?
This is classic multi-way merge: Create a heap of pairs (element, which list did it come from). Initialize with first elements of each list. Repeatedly remove the minimum element and add the next element from its originating list.

Also discussed before at https://stackoverflow.com/questions/5055909/algorithm-for-n-way-merge .