You wish to find the median of n data stored in a CD-ROM using a computer that has O(log n) read/write memory. Use an O(n log n) expected time algorithm to find the median without writing to disk. Please provide :
- the algorithm, including pseudocide.
- a prove to show the algorithm is correct
- an analysis of running time of the algorithm