реализация медианы scala

Какая быстрая реализация медианы в scala?

Вот что я нашел в коде розетты :

  def median(s: Seq[Double])  =
  {
    val (lower, upper) = s.sortWith(_<_).splitAt(s.size / 2)
    if (s.size % 2 == 0) (lower.last + upper.head) / 2.0 else upper.head
  }

Мне это не нравится, потому что он выполняет сортировку. Я знаю, что это являются способами вычисления медианы за линейное время.

РЕДАКТИРОВАТЬ:

Я хотел бы иметь набор медианных функций, которые я мог бы использовать в различных сценариях:

1. быстрое вычисление медианы на месте, которое может быть выполнено в медиана линейного времени
2. , которая работает с потоком, который можно пересечь несколько раз, но вы можете хранить только O (log n) значений в памяти , как эта
3. медиана, которая работает в потоке, где вы можете хранить не более O (log n) значения в памяти, и вы можете пройти поток не более одного раза (возможно ли это?)

Пожалуйста, разместите только код, который компилирует , а правильно вычисляет медианное значение . Для простоты можно предположить, что все входные данные содержат нечетное количество значений.