source: applications/trunk/UGPSummerSchool2008/src/Sort.rf @ 3840

$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);