Как написать "универсальную" сортировку в Scala?

Question

Вот что у меня так далеко:

  def mergesort[T <: Ordered[T]](elements : List[T]) : List[T] = {
    def merge(first : List[T], second : List[T]) : List[T] = (first, second) match {
      case (Nil, _) => second
      case (_, Nil) => first
      case (x :: xs, y :: ys) => if (x < y) x :: merge(xs, second) else y :: merge(first, ys)
    }

    if (elements.isEmpty) Nil
    else {
      val length = elements.length
      val (firstHalf, secondHalf) = elements.splitAt(length/2)

      merge(mergesort(firstHalf), mergesort(secondHalf))
    }
  }

У меня проблема в том, что это не удается

mergesort(List(1, 3, 6, 3, 1, 0))

error: inferred type arguments [Int] do not conform to method mergesort's type parameter bounds [T <: Ordered[T]]
       mergesort(List(1, 3, 6, 3, 1, 0))
       ^

Есть ли способ сделать эту работу для всех типов, которые заказаны? Я думал, что у Scala будет какое-то неявное преобразование в "богатый" целочисленный тип, который, как я предполагал, будет иметь Ordered черта характера.

Answer 1

Что вам нужно, так это вид def mergesort[T <% Ordered[T]], См. Ответы на этот вопрос: универсальный метод для возврата первого из двух значений.

Теперь это будет выполнено, но в вашем алгоритме есть некоторые ошибки, приводящие к ошибке переполнения стека в splitAt линия.