shithub: mc

ref: fe0c54bda8e70766480784336fc881567620410e
dir: /lib/std/sort.myr/

use "cmp"

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
			-> void
		;;
	;;
}