7 ms·

Here is a python implementation. https://github.com/NSkelsey/algorithms/blob/master/select.py https://github.com/NSkelsey/algorithms/blob/master/select.py

• ratpik 13y ago
  Sorting the sub-lists to find the 5 medians by itself is at best a O(nlogn) as per this example. That would make the algorithm non O(n). Or am I missing something?
  • virgi1 13y ago
    Yes you are. It's O(nlogn) where n is 5 - i.e. it's constant time (you can easily find the median by 4 comparisons to find the smallest of the 5, followed by 3 comparisons for the 2nd smallest, followed by 2 comparisons for the median - a total of 9 comparisons)
    • ihateloggingin 13y ago
      Put otherwise: to sort them all it's O(n/5*(5 log 5)) = O(n).