shithub: mc

ref: 779a3ef073261c6919ec2a65545435a35a3f5b6f
dir: /libstd/sort.myr/

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], 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 = r*2 + 1
		s = r
		match cmp(sl[s], sl[c])
		| `Before:	s = c
		;;
		if c + 1 < sl.len
			match cmp(sl[s], sl[c + 1])
			| `Before:	s = c + 1
			;;
		;;
		if s != r
			tmp = sl[r]
			sl[r] = sl[s]
			sl[s] = tmp
			r = s
		else
			->
		;;
	;;
}