summaryrefslogtreecommitdiff
path: root/lib/std/sort.myr
blob: dbf48d380e7fc67c045fd3641d2b8326c843643a (plain)
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
			->
		;;
	;;
}