How to find the "joint" median of 3 sorted lists, in less than linear time?

Question

We are given 3 sorted lists of size: n1, n2 and n3.  We want to find the median of the merged list.  Can we do that in less than linear time?  If so, how?

Answer 1

In some degree, this problem is similar to median of medians algorithm we talk about in class (I use MOM to represent it in following answers).

The similarity is we can also use median of medians to eliminate impossible portion of lists and then recursively call algorithm. The logic here is straightforward: 

1. select three medians of 3 lists (m1, m2 and m3 map to n1, n2 and n3) and then sort them. Based on 3 lists have already been sorted, this step only needs constant time to complete. O(1)
2. Then next is the primary observation: let's suppose in step 1: m1<m2<m3 . In this case, we can know first half of list n1 and second half of list n3 are eliminated. Here the logic is similar to MOM, because the first half of n1 are less than median of medians then they are impossible to be median of whole merged list. Also the second half of n3 are greater than median of medians then they are also impossible to be candidate. But in order to keep the final median same, we have to eliminate same length of lists on both side. So we need to compare length of n1 and n3 to find one that has smaller length and eliminate this length / 2 on both sides. The only difference within this problem and MOM is, in MOM because we deal with an unsorted list, so we can only make sure the final median is between 3/10 and 7/10 of list and we need to use median of medians to partition and eliminate some numbers. But in this problem, because all lists are sorted, we can eliminate two parts simultaneously. For a summary: every time we compare length of two lists that have smallest median and largest median to find a smaller length, and then eliminate lists with this length / 2 on smallest median list from beginning and largest median list from end. This step also require constant time. O(1)
3. Remaining things are easy, we can recursively call algorithm until we find the final median.

Consider the time complexity of this algorithm, let n = n1 + n2 + n3 (this is the size of merged list). every time we call the algorithm we eliminate smaller length / 2 from two lists. But no matter how many numbers are actually eliminated, the remaining part is a number less than n, let's say k*n (k < 1). Plus every time we use constant time to find median of medians and this smaller length. The recurrence relation can then be represented as: T(n) = T(kn) + c, which k < 1. Use master theorem we can easily now the total time complexity is: O(logn).

By the way, if we consider a general case: say we have m sorted list. Then the final complexity should be (m logn).

Comments

You can claim that  T(n) = T(kn) + c, which k < 1 leads to O(log n) only if you can prove that k is a certain value, such as 0.5 or 0.9 or 0.99.  Merely saying k < 1 is not enough, because for example, k could be (n-1)/n, which would mean: T(n) = T(n-1) + c.

---

yes, a easy example is every time delete 2 number and the time is n/2

Answer 2

Change this question to find the medium of n sorted list n1~nn

Comments

the medium of odd is medium, the medium of even is the first unmber