Does anyone know? can't think of any good idea as best run time is already O(log(N)). Please help, thanks!!
Facebook interview followup: how to improve if called multiple times

I was thinking of another approach that is not mentioned here yet. Put everything into a priority queue(I understand that the input is already in sorted order). Do the bunch of inserts(really a huge number). This is to make sure after all the inserts the values are still in sorted order.
Then just go ahead and perform the merge in the end. This way the worst case complexity will be O(n logn).