Median Of Medians

medianOfMedians.hs

import Data.List

median :: (Show a, Ord a) => [a] -> a
median xs = select ((length xs) `div` 2) xs

select :: (Show a, Ord a) => Int -> [a] -> a
select i xs
  | n <= 5                        = (sort xs) !! i
  | lengthLower == i  = medianOfMedians
  | lengthLower < i   = select (i - lengthLower - 1) upperPartition
  | otherwise         = select i lowerPartition
  where
    n = length xs
    medianOfMedians = median (map median (chunksOf 5 xs))
    (lowerPartition, _:upperPartition) = partition (\x -> x < medianOfMedians) xs
    lengthLower = length lowerPartition
    chunksOf :: Int -> [a] -> [[a]]
    chunksOf _ [] = []
    chunksOf n xs = (take n xs) : (chunksOf n (drop n xs))

medianOfMedians.py

def select(A, i):
    if len(A) <= 5:
        return sorted(A)[i]
    chunks = [A[i:i + 5] for i in range(0, len(A), 5)]
    medians = [select(chunk, len(chunk)//2) for chunk in chunks]
    medianOfMedians = select(medians, len(medians)//2)
    lowerPartition, upperPartition = [a for a in A if a < medianOfMedians], [a for a in A if a > medianOfMedians]
    if i == len(lowerPartition):
        return medianOfMedians
    elif i > len(lowerPartition):
        return select(upperPartition, i - len(lowerPartition) - 1)
    else:
        return select(lowerPartition, i)