Вот'Моя реализация сортировки слиянием в Scala:

object FuncSort {
  def merge(l: Stream[Int], r: Stream[Int]) : Stream[Int] = {
    (l, r) match {
      case (h #:: t, Empty) => l
      case (Empty, h #:: t) => r
      case (x #:: xs, y #:: ys) => if(x < y ) x #:: merge(xs, r) else y #:: merge(l, ys)
    }
  }

  def sort(xs: Stream[Int]) : Stream[Int] = {
    if(xs.length == 1) xs
    else {
      val m = xs.length / 2
      val (l, r) = xs.splitAt(m)
      merge(sort(l), sort(r))
    }
  }
}

Это работает правильно, и кажется, что асимптотически это хорошо, но это намного медленнее (примерно в 10 раз), чем реализация Java отсюдаhttp://algs4.cs.princeton.edu/22mergesort/Merge.java.html и использует много памяти. Есть ли более быстрая реализация сортировки слиянием, котораяфункциональная? Очевидно, этоможно портировать версию Java построчно, но этоне то, что яищу

UPD: ямы изменилисьStream вList а также#:: в:: и процедура сортировки стала быстрее, всего в три-четыре раза медленнее, чем версия Java. Но я нене понимаю, почему нет вылетает с переполнением стека?merge ISN»t-рекурсивный, все аргументы строго оценены ... как это возможно?