From 55f277e77428d7423ae906a8e1f1324d35b07a7d Mon Sep 17 00:00:00 2001 From: Jakob Kaivo Date: Fri, 4 Mar 2022 12:32:20 -0500 Subject: import Miranda 2.066 from upstream --- miralib/ex/treesort.m | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 miralib/ex/treesort.m (limited to 'miralib/ex/treesort.m') diff --git a/miralib/ex/treesort.m b/miralib/ex/treesort.m new file mode 100644 index 0000000..e5b946b --- /dev/null +++ b/miralib/ex/treesort.m @@ -0,0 +1,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] + -- cgit v1.2.1