20060303a

1 files changed, 36 insertions, 0 deletions

diff --git a/appl/lib/sort.b b/appl/lib/sort.b
new file mode 100644
index 00000000..a425845e
--- /dev/null
+++ b/appl/lib/sort.b
@@ -0,0 +1,36 @@
+implement Sort;
+include "sort.m";
+
+sort[S, T](s: S, a: array of T)
+	for{
+	S =>
+		gt: fn(s: self S, x, y: T): int;
+	}
+{
+	mergesort(s, a, array[len a] of T);
+}
+
+mergesort[S, T](s: S, a, b: array of T)
+	for{
+	S =>
+		gt: fn(s: self S, x, y: T): int;
+	}
+{
+	r := len a;
+	if (r > 1) {
+		m := (r-1)/2 + 1;
+		mergesort(s, a[0:m], b[0:m]);
+		mergesort(s, a[m:], b[m:]);
+		b[0:] = a;
+		for ((i, j, k) := (0, m, 0); i < m && j < r; k++) {
+			if(s.gt(b[i], b[j]))
+				a[k] = b[j++];
+			else
+				a[k] = b[i++];
+		}
+		if (i < m)
+			a[k:] = b[i:m];
+		else if (j < r)
+			a[k:] = b[j:r];
+	}
+}