$module Sort;

$use Compare StdIO;

$func Sort e.list = e.list;

Sort {
	/* empty */   = /* empty */;
	s.head e.tail = <Split s.head e.tail> :: (e.smaller) (e.greater),
		<Sort e.smaller> s.head <Sort e.greater>;
};

$func Split s.num e.list = (e.list) (e.list);

Split s.num e.list, e.list : {
	/* empty */   = () ();
	s.head e.tail = <Split s.num e.tail> :: (e.smaller) (e.greater), {
		<Le (s.head) (s.num)> = (s.head e.smaller) (e.greater);
		(e.smaller) (s.head e.greater);
	};
};

$func Main = e;

Main, <WriteLn <Sort 1 5 2 5 2 1>>;



$func Split2 s.num e.list = (e.list) (e.list);

Split2 s.num e.list, 
	() () (e.list) $iter {
		e.list : s.head e.tail, {
			<Le (s.head) (s.num)>,
				(e.smaller s.head) (e.greater) (e.tail);
			(e.smaller) (e.greater s.head) (e.tail);
		};
	} :: (e.smaller) (e.greater) (e.list),
	e.list : /*empty*/,
	(e.smaller) (e.greater);