Add std.sort, with a simple mergesort.

3 files changed, 100 insertions, 0 deletions

diff --git a/src/lib/sort.rs b/src/lib/sort.rs
new file mode 100644
index 00000000000..cff7efce9c2
--- /dev/null
+++ b/src/lib/sort.rs
@@ -0,0 +1,49 @@
+import _vec.len;
+import _vec.slice;
+
+type lteq[T] = fn(&T a, &T b) -> bool;
+
+fn merge_sort[T](lteq[T] le, vec[T] v) -> vec[T] {
+
+  fn merge[T](lteq[T] le, vec[T] a, vec[T] b) -> vec[T] {
+    let vec[T] res = vec();
+    let uint a_len = len[T](a);
+    let uint a_ix = 0u;
+    let uint b_len = len[T](b);
+    let uint b_ix = 0u;
+    while (a_ix < a_len && b_ix < b_len) {
+      if (le(a.(a_ix), b.(b_ix))) {
+        res += a.(a_ix);
+        a_ix += 1u;
+      } else {
+        res += b.(b_ix);
+        b_ix += 1u;
+      }
+    }
+    res += slice[T](a, a_ix, a_len);
+    res += slice[T](b, b_ix, b_len);
+    ret res;
+  }
+
+  let uint v_len = len[T](v);
+
+  if (v_len <= 1u) {
+    ret v;
+  }
+
+  let uint mid = v_len / 2u;
+  let vec[T] a = slice[T](v, 0u, mid);
+  let vec[T] b = slice[T](v, mid, v_len);
+  ret merge[T](le,
+               merge_sort[T](le, a),
+               merge_sort[T](le, b));
+}
+
+// Local Variables:
+// mode: rust;
+// fill-column: 78;
+// indent-tabs-mode: nil
+// c-basic-offset: 4
+// buffer-file-coding-system: utf-8-unix
+// compile-command: "make -k -C .. 2>&1 | sed -e 's/\\/x\\//x:\\//g'";
+// End:
diff --git a/src/lib/std.rc b/src/lib/std.rc
index e00f2ef2eb2..b5a1030be07 100644
--- a/src/lib/std.rc
+++ b/src/lib/std.rc
@@ -55,6 +55,7 @@ mod list;
 mod rand;
 mod dbg;
 mod bitv;
+mod sort;
 
 // Local Variables:
 // mode: rust;
diff --git a/src/test/run-pass/lib-sort.rs b/src/test/run-pass/lib-sort.rs
new file mode 100644
index 00000000000..e2c3465cdfd
--- /dev/null
+++ b/src/test/run-pass/lib-sort.rs
@@ -0,0 +1,50 @@
+use std;
+
+fn check_sort(vec[int] v1, vec[int] v2) {
+  auto len = std._vec.len[int](v1);
+  fn lteq(&int a, &int b) -> bool {
+    ret a <= b;
+  }
+  auto f = lteq;
+  auto v3 = std.sort.merge_sort[int](f, v1);
+  auto i = 0u;
+  while (i < len) {
+    log v3.(i);
+    check (v3.(i) == v2.(i));
+    i += 1u;
+  }
+}
+
+fn main() {
+  {
+    auto v1 = vec(3,7,4,5,2,9,5,8);
+    auto v2 = vec(2,3,4,5,5,7,8,9);
+    check_sort(v1, v2);
+  }
+
+  {
+    auto v1 = vec(1,1,1);
+    auto v2 = vec(1,1,1);
+    check_sort(v1, v2);
+  }
+
+  {
+    let vec[int] v1 = vec();
+    let vec[int] v2 = vec();
+    check_sort(v1, v2);
+  }
+
+  {
+    auto v1 = vec(9);
+    auto v2 = vec(9);
+    check_sort(v1, v2);
+  }
+
+  {
+    auto v1 = vec(9,3,3,3,9);
+    auto v2 = vec(3,3,3,9,9);
+    check_sort(v1, v2);
+  }
+
+}
+