1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
object MergeSort
{
import math.Ordering
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[T], ys: List[T]): List[T] = (xs, ys) match {
case (Nil, ys) => ys
case (xs, Nil) => xs
case (x :: xs1, y :: ys1) => {
if (lt(x, y)) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
}
val (fst, snd) = xs splitAt n
merge(msort(fst)(lt), msort(snd)(lt))
}
}
/* 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)
}
}
|
