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

One possible solution is to use the "median of medians" algorithm, which has a worst-case time complexity of O(n). Here are the steps:

1. Divide each list into smaller sublists of size 5.
2. Find the median of each sublist using a simple sorting algorithm (e.g. insertion sort).
3. Take the median of the medians as a pivot.
4. Partition each list around the pivot, so that all elements smaller than the pivot are on the left, and all elements larger than the pivot are on the right.
5. If the pivot is the joint median, return it.
6. If the pivot is smaller than the joint median, recursively repeat the algorithm on the right half of each list.
7. If the pivot is larger than the joint median, recursively repeat the algorithm on the left half of each list.

The "median of medians" algorithm guarantees that the pivot is at least the median of (n/5) medians, so it is close to the true median. By partitioning the lists around the pivot, we can eliminate at least one-third of the elements in each iteration. Therefore, the algorithm has a worst-case time complexity of O(n), which is less than linear.