4 files changed, 80 insertions, 0 deletions
diff --git a/sample/sort/bsort.in b/sample/sort/bsort.in
new file mode 100644
index 0000000..7b2e2d6
--- /dev/null
+++ b/sample/sort/bsort.in
@@ -0,0 +1,18 @@
+// Bubble sort
+
+// Rules
+bsort(ret) >< [] => ret~[];
+bsort(ret) >< x:xs => bsort(ret)~cnt, bubble(cnt, x)~xs;
+bsort(ret) >< M(x) => ret~x;
+
+bubble(ret, int x) >< [] => ret~M([x]);
+bubble(ret, int x) >< M(w) => ret~M(x:w);
+bubble(ret, int x) >< (int y):ys
+| x<y => ret~(x:cnt), bubble(cnt, y)~ys
+| _   => ret~(y:cnt), bubble(cnt, x)~ys;
+
+
+// Nets
+bsort(r)~[3,6,1,9,2];
+r;
+
diff --git a/sample/sort/isort.in b/sample/sort/isort.in
new file mode 100644
index 0000000..e637055
--- /dev/null
+++ b/sample/sort/isort.in
@@ -0,0 +1,15 @@
+// Insertion sort
+
+// Rules
+isort(ret) >< [] => ret~[];
+isort(ret) >< x:xs => insert(ret, x)~cnt, isort(cnt)~xs;
+
+insert(ret, int x) >< [] => ret~[x];
+insert(ret, int x) >< (int y):ys
+| x<=y => ret~(x:y:ys)
+| _    => ret~(y:cnt), insert(cnt, x)~ys;
+
+
+// Nets
+isort(r)~[3,6,1,9,2];
+r;
diff --git a/sample/sort/msort.in b/sample/sort/msort.in
new file mode 100644
index 0000000..599990b
--- /dev/null
+++ b/sample/sort/msort.in
@@ -0,0 +1,28 @@
+// Merge sort
+
+// Rules
+msort(ret) >< [] => ret~[];
+msort(ret) >< x:xs => ms_tail(ret, x)~xs;
+
+ms_tail(ret, n) >< [] => ret~[n];
+ms_tail(ret, n) >< x:xs => 
+	split(left,right) ~ (n:x:xs),
+	msort(a)~left, msort(b)~right, merge(ret,b)~a;
+
+merge(ret, snd) >< [] => ret~snd;
+merge(ret, snd) >< x:xs => mergeCC(ret, x, xs)~snd;
+
+mergeCC(ret, int y, ys) >< [] => ret~(y:ys);
+mergeCC(ret, int y, ys) >< (int x):xs
+| x <= y => ret~(x:cnt), mergeCC(cnt, y, ys) ~ xs
+| _      => ret~(y:cnt), mergeCC(cnt, x, xs) ~ ys;
+
+
+split(right,left) >< [] => right~[], left~[];
+split(right,left) >< x:xs =>
+	right~(x:cntl), left~cntr, split(cntr,cntl)~xs;
+
+
+// Nets
+msort(ret)~[3,6,1,9,2];
+ret;
+\ No newline at end of file
diff --git a/sample/sort/qsort.in b/sample/sort/qsort.in
new file mode 100644
index 0000000..523d7d8
--- /dev/null
+++ b/sample/sort/qsort.in
@@ -0,0 +1,19 @@
+// Quick sort
+
+// Rules
+qsort(ret) >< [] => ret~[];
+qsort(ret) >< (int x):xs =>
+	Append(ret, x:right)~left, part(smaller, larger, x)~xs,
+	qsort(left)~smaller, qsort(right)~larger;
+
+// Note: `Append' is implemented as the following built-in agent:
+// Append(ret, b)~a  -->  ret ~ (a++b)
+
+part(smaller, larger, int x) >< [] => smaller~[], larger~[];
+part(smaller, larger, int x) >< (int y):ys
+| y<x => smaller~(y:cnt), part(cnt, larger, x)~ys
+| _   => larger~(y:cnt), part(smaller, cnt, x)~ys;
+
+// Nets
+qsort(ret)~[3,6,1,9,2];
+ret;
+\ No newline at end of file