The best way to keep track of the median

The normal merge sort algorithm - merge step with normally apply n + m -1 comparisons, where one list is of size n and and the other list is of size m. Using this algorithm is the most simplest approach to combine two sorted lists.

If the comparisons are too expensive you could do two things - either you minimize the number of comparisons or you minimize the cost of comparisons.

Let's focus on the minimization of the cost of comparison. You and only you can decide whether the data you are comparing can be quantized or not. If you can quantize them, which is a form of implementing a hash method, which is keeping the ordering. E.g. if your Data is compared by Name, Then the first tname, ... you can take the first to Chars of the name "Klaehn, Ruediger" and reduce/quantize your data element to "Kl.Ru", if you compare it to "Packer, The" you preserve the ordering "Pa.Th" - you can now apply a cheaper comparison algorithm, comparing the reduced values. But if you find another "Kl.Ru", you now have a near value, and you might now switch to a more expensive approach comparing these elements.

If you can extract this quantized value from your data, faster than comparing it, this is the first thing you do, you compare the quantized or hashed value first. Please keep in mind, that this value needs to be computed only once, so you can compute it on creating the data element.

I also mentioned another way, to minimize your comparisons.

I had a look into the classic book TAOCP- Volume 3-Sorting and Searching, (pp.197-207, section 5.3.2) which has full 10 pages on this topic. I found two references to algorithms which are faster than n+m-1 comparisons.

First there is the Hwang-Lin merge algorithm and the second an improvement by Glenn K Manacher - both are cited by TAOCP as well as an algorithm by Christen, which approaches the lower bound of needed comparisons, on special conditions on the length n and m of the lists.

The algorithm of Manacher was presented in Journal of the ACM Vol. 26 Number 3 on pages 434-440: "Significant Improvements to the "Hwan-Lin" Merging Algorithm". the list with m items and the list with n items can be of different length, but they must also be odered by the numbers of elements they contain m<=n

The Hwang-Lin algorithm breaks the lists to merge, apart to smaller lists and sorts the lists by comparing the first element of each sublist, and to decide whether some elements in the sublist need to be compared or not. If the first list is smaller than the second list, then the chance is high, that consecutive elements of the longer list can be transferred into the resulting list without comparison. If the first element of the small ist is greater than the first element of the splitted larger list, all elements in front of sublist can be copied without comparison.

Average case analysis of the merging alorithm of Hwang and Lin (Vega, Frieze, Santha) in Section 2 you can find a pseudocode of the HL-Algorithm. Which is a lot better than my description. And you can see why there are fewer comparisons - the algorithm uses a binary search, to find the index, where to insert the element from the shorter list.

If the lists are not interleaved like in your last example, you should have a remaining smaller and a remaining larger list in most cases. This is when the the HL-algorithm starts to perform better.

If it is truly an ordered linked list, this should be a fairly bad choice because you have to traverse the list one by one until you find the right place to insert the item. In other words O(N). This is ok if the list is small but can get out of hand for big graphs.

Usually, what you will need for that kind of stuff is a heap:

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

...where you can insert and pop in O(log(n)) ...it's also usually available out of the box in most programming languages.