summaryrefslogtreecommitdiff
path: root/miralib/ex/treesort.m
diff options
context:
space:
mode:
authorJakob Kaivo <jkk@ung.org>2022-03-04 12:32:20 -0500
committerJakob Kaivo <jkk@ung.org>2022-03-04 12:32:20 -0500
commit55f277e77428d7423ae906a8e1f1324d35b07a7d (patch)
tree5c1c04703dff89c46b349025d2d3ec88ea9b3819 /miralib/ex/treesort.m
import Miranda 2.066 from upstream
Diffstat (limited to 'miralib/ex/treesort.m')
-rw-r--r--miralib/ex/treesort.m20
1 files changed, 20 insertions, 0 deletions
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]
+