Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | fun cp [] =[] |
2 | | cp (x::xs)= x :: cp xs | |
3 | ||
4 | (* exormorphic merge *) | |
5 | fun merge(xs, []):int list = cp xs | |
6 | | merge([], ys) = cp ys | |
7 | | merge(l1 as x::xs, l2 as y::ys) = | |
8 | if x<y then x :: merge(xs, l2) | |
9 | else y :: merge(l1, ys) | |
10 | ||
11 | (* splitting a list *) | |
12 | fun split(x::y::zs, l, r) = split(zs, x::l, y::r) | |
13 | | split([x], l, r) = (x::l, r) | |
14 | | split([], l, r) = (l, r) | |
15 | ||
16 | (* exomorphic merge sort *) | |
17 | fun msort [] = [] | |
18 | | msort [x] = [x] | |
19 | | msort xs = let val (l, r) = split(xs, [], []) | |
20 | in merge(msort l, msort r) | |
21 | end; |