If they truly are lists (i.e. not random access) then nothing will give you that. If you have the head elements of the lists and you want the median then you have to traverse (m+n)/2 elements just to get to the median. There is no way around that. If you translate the lists to arrays then that’s an o(n+m) operation in itself.