Andrew Chambersadd mktempat to stdb44b19310 years agoHistory
61 lines · 801 B · Text
RawDownload
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		;;	;;}