From a92840a4e19676b0b6afc916d0a65243f42dc5e5 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Thu, 9 May 2013 21:29:43 +0200 Subject: Scala : generalize merge sort --- Scala/sandbox/10-merge-sort.scala | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) diff --git a/Scala/sandbox/10-merge-sort.scala b/Scala/sandbox/10-merge-sort.scala index 92296e2..5cf0b44 100644 --- a/Scala/sandbox/10-merge-sort.scala +++ b/Scala/sandbox/10-merge-sort.scala @@ -1,25 +1,27 @@ object MergeSort { - def msort(xs: List[Int]): List[Int] = { + def msort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = { val n = xs.length/2 if (n==0) xs else { - def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match { + def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match { case (Nil, ys) => ys case (xs, Nil) => xs case (x :: xs1, y :: ys1) => { - if (x < y) x :: merge(xs1, ys) + if (lt(x, y)) x :: merge(xs1, ys) else y :: merge(xs, ys1) } } val (fst, snd) = xs splitAt n - merge(msort(fst), msort(snd)) + merge(msort(fst)(lt), msort(snd)(lt)) } } def run = { println("MergeSort") - println(msort(List(2, 8, -2, 9, 2, 6, 0, 7, 1))) + val nums = List(2, 8, -2, 9, 2, 6, 0, 7, 1) + val sorted = msort(nums)((x: Int, y: Int) => x < y) + println(sorted) } } -- cgit v1.1-2-g2b99