3 ms·
For reference, finding the median is an O(n) problem on a single computer, and sorting is an O(n log n) solution. An O(n) algorithm is Quick select. It is basi
by im3w1l 13y ago
For reference, finding the median is an O(n) problem on a single computer, and sorting is an O(n log n) solution.
An O(n) algorithm is Quick select. It is basically like quick sort but you only recurse on the side of the pivot that contains the median.
http://en.wikipedia.org/wiki/Quickselect http://en.wikipedia.org/wiki/Quickselect