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
|
object MergeSort
{
def msort(xs: List[Int]): List[Int] = {
val n = xs.length/2
if (n==0) xs
else {
def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {
case (Nil, ys) => ys
case (xs, Nil) => xs
case (x :: xs1, y :: ys1) => {
if (x < y) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
}
val (fst, snd) = xs splitAt n
merge(msort(fst), msort(snd))
}
}
def run = {
println("MergeSort")
println(msort(List(2, 8, -2, 9, 2, 6, 0, 7, 1)))
}
}
|
