diff options
| -rw-r--r-- | Scala/sandbox/10-merge-sort.scala | 23 |
1 files changed, 23 insertions, 0 deletions
diff --git a/Scala/sandbox/10-merge-sort.scala b/Scala/sandbox/10-merge-sort.scala index 5cf0b44..04aa38d 100644 --- a/Scala/sandbox/10-merge-sort.scala +++ b/Scala/sandbox/10-merge-sort.scala @@ -1,5 +1,6 @@ object MergeSort { + import math.Ordering def msort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = { val n = xs.length/2 @@ -18,10 +19,32 @@ object MergeSort } } + /* def msortO[T](xs: List[T])(ord: Ordering[T]): List[T] = { */ + def msortO[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = { + val n = xs.length/2 + if (n==0) xs + else { + 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 (ord.lt(x, y)) x :: merge(xs1, ys) + else y :: merge(xs, ys1) + } + } + val (fst, snd) = xs splitAt n + /* merge(msortO(fst)(ord), msortO(snd)(ord)) */ + merge(msortO(fst), msortO(snd)) + } + } + def run = { println("MergeSort") val nums = List(2, 8, -2, 9, 2, 6, 0, 7, 1) val sorted = msort(nums)((x: Int, y: Int) => x < y) println(sorted) + /* val sorted2 = msortO(nums)(Ordering.Int) */ + val sorted2 = msortO(nums) + println(sorted2) } } |