What is the correct answer to this? Let's try a little experiment.. I've never heard this question before, so I'm in the same boat as a naive interviewer right now. Let me elaborate my thought process.

"H'm, this looks a bit like mergesort, where you take two sorted sublists and form a bigger sorted list. So...sort the sublists using mergesort, then call the merging algorithm? (compare the heads of the two lists, and form the bigger list)"

This would be the answer I'd start giving. Tell me if it corresponds even remotely with what your idea of a correct answer is, or what points would you deduct from if it is incorrect. Off the top of my head, I'm not sure I'd be able to write the exact python code for this that covers all edge cases in less than 15 minutes.