Suppose we have an external disk with $n$ unsorted records. ($n$ is incredibly large). We want to find the median of this $n$ elements but we can only load $O(\lg n$) records to the memory at the same time. Also the disk is read-only. Design an $O(n \lg n)$ algorithm for this.
It is the first time I see a problem that cannot be solved using main memory and needs external disk. After some search, I found some algorithms for external sorting but it seem that it is not the case here because it doesn't want complete sorting.
What should I do to solve problems like this?