Mergesort in Scala

Und aus der Kategorie "Sortieren für Besessene" kommt heute mal wieder ein Beispiel, aber ausnahmsweise kein Quicksort ;)

Was ich besonders toll an diesem Beispiel finde ist das auf gleich 2 Listen gleichzeitig gematcht wird wie es auch in Haskell geht. Da hat Scala mal wieder richtig Spass gemacht.

object Main {

  def merge[T <% Ordered[T]](l: List[T], r: List[T]): List[T] = 
    (l,r) match {
      case (x::xs, y::ys) => if (x < y)
                               x::(merge(xs, r)) 
                             else
                               y::(merge(l, ys))
      case (xs,  Nil) => xs
      case (Nil, ys)  => ys
    }   

  def mergesort[T <% Ordered[T]](list: List[T]): List[T] =   
    if (list.length > 1) { 
      val (l, r) = list splitAt (list length)/2
      merge(mergesort(l), mergesort(r))
    } else list

  def main(args: Array[String]): Unit = { 
    println(mergesort(List(4,5,9,1,2,4,5,9,8,7)))
  }
}