summaryrefslogtreecommitdiff
path: root/lib/std/sort.myr
diff options
context:
space:
mode:
Diffstat (limited to 'lib/std/sort.myr')
-rw-r--r--lib/std/sort.myr61
1 files changed, 61 insertions, 0 deletions
diff --git a/lib/std/sort.myr b/lib/std/sort.myr
new file mode 100644
index 0000000..dbf48d3
--- /dev/null
+++ b/lib/std/sort.myr
@@ -0,0 +1,61 @@
+use "cmp.use"
+
+pkg std =
+ generic sort : (sl:@a[:], cmp:(a:@a, b:@a -> order) -> @a[:])
+;;
+
+generic sort = {sl, cmp
+ var end
+ var tmp
+
+ heapify(sl, cmp)
+ end = sl.len - 1
+ while end > 0
+ tmp = sl[end]
+ sl[end] = sl[0]
+ sl[0] = tmp
+ end--
+ siftdown(sl[:end + 1], 0, cmp)
+ ;;
+ -> sl
+}
+
+generic heapify = {sl, cmp
+ var start
+
+ start = sl.len/2 - 1
+ while start >= 0
+ siftdown(sl, start, cmp)
+ start--
+ ;;
+}
+
+generic siftdown = {sl, start, cmp
+ var r, c, s
+ var tmp
+
+ r = start
+ while 2*r + 1 < sl.len
+ c = 2*r + 1
+ s = r
+ match cmp(sl[s], sl[c])
+ | `Before: s = c
+ | _: /* nothing */
+ ;;
+ if c + 1 < sl.len
+ match cmp(sl[s], sl[c + 1])
+ | `Before: s = c + 1
+ | _: /* nothing */
+ ;;
+ ;;
+ if s != r
+ tmp = sl[r]
+ sl[r] = sl[s]
+ sl[s] = tmp
+ r = s
+ else
+ ->
+ ;;
+ ;;
+}
+