Montag, 10. Mai 2010

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)))
}
}