I think your previous solution was more efficient, this one keesp repeatedly searching the lowerbound, the prior compared as interleaving

This is the way, I would only change a few minor things

Bello !

You're absolutely right, but the original one explicitly excluded std::merge :)

You could save some occurances of std::list<int>::iterator::operator++ if you take it out of the for header, remove the assignment to the return value of std::list<int>::insert, and add and else, but this preserves the ideas of the forked Python solution better.

Yes, I hadn't thought of the complexity of list.insert in particular (list.pop(0) is basically just n,list=list[0],list[1:];return n so I don't think it's too bad, but it's possible I just don't understand how slicing works under the hood). Also, I will admit I was tempted to try and golf this answer, but that would probably just lead to lambda a,b:sorted(a+b) as mentioned in the original, so that's pretty boring.