sort.ast

------------------------------------------------------------------
-- sort.ast
--
-- defines a parameterized sort function over a list.  it uses
-- a user defined order predicate on elements of the list to
-- perform the sort. the underlying sort algorithm is the
-- Quicksort.
--
-- Example:
--  sort((lambda with (x,y) do return true if x<y else false),
--       [10,5,110,50]).
--
-- (c) University of Rhode Island
------------------------------------------------------------------

------------------------------------------------------------------
function sort
------------------------------------------------------------------
    with (_,[]) do
        return [].
    with (_,[a]) do
        return [a].
    with (p,[pivot|rest]) do
        let less=[].
        let more=[].

        for e in rest do
            if p(e,pivot) do
                let less = less + [e].
            else
                let more = more + [e].
            end
        end

        return sort(p,less) + [pivot] + sort(p,more).
end