blob: e5b946b7d620d4c9fd4743f98a42d2ab0b04528f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
|| Here is another sorting algorithm, this time treesort.
|| to try it out, say: treesort testdata
tree * ::= NILT | NODE * (tree *) (tree *)
treesort = flatten.build
build::[*]->tree *
build = foldr insert NILT
insert b NILT = NODE b NILT NILT
insert b (NODE a x y) = NODE a (insert b x) y, if b<=a
= NODE a x (insert b y), if b>a
flatten::tree *->[*]
flatten NILT = []
flatten (NODE a x y) = flatten x ++ [a] ++ flatten y
testdata = [1..5]++[20,19..16]++[6..10]++[15,14..11]
|
