1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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
->
;;
;;
}
|
