How to efficiently find the median value of two sorted lists

The solution I found is a relatively simple dichotomic search alorithm with a logaritmic complexity in the worst case.

Here is an exemple of how it works. Imagine we have these two sorted lists:

l1 = [1, 4, 5, 7, 7, 8, 9, 9]
l2 = [0, 1, 3, 6, 6, 6, 7, 8]

We calculate the median of both lists:

l1 median = 7
l2 median = 6

l1 median is greater than l2 median so we can safely remove the numbers on the right side of the median of l1 because the final median is somewhere between the median of both. We also have to remove the same amount of numbers at the left side of l2 to keep the stability of the final list. If one of the list is shorter the amount of removed numbers will the minimum between both median index. So we get:

l1 = [1, 4, 5, 7, 7]
l2 = [6, 6, 6, 7, 8]

We continue the process until have a list with 2 numbers (or less).

l1 median = 5
l2 median = 6

We remove 2 from left side of l1, we remove 2 from right side of l2.

l1 = [5, 7, 7]
l2 = [6, 6, 6]

l1 median = 7
l2 median = 6

We remove 1 from left side of l2, we remove 1 from right side of l1.

l1 = [5, 7]
l2 = [6, 6]

Remember that we have 2 list of the same size. In another case one could be an order of magnitude bigger than the other. Finally we have to deal with some special case:

1. The 2 remaining numbers have to be inserted on the left side of the median of the other list.
2. The 2 remaining numbers have to be inserted on the right side of the median of the other list.
3. One have to be inserted on the left side of the median and the other on the right side.

For each case we have to check if the number could change the median of the resulting list. If we decide to insert l1 into l2, there will be no implication on the initial median value of l2. But if we decide to insert l2 into l1, the median of l1 will be completely changed. In both case we obtain this list [5, 6, 6, 7] and calculate the median of it : 6.

Inserting the two remaining value into the other list is not the fastest thing possible but it’s simple and understandable.