(* * * * * * * * * * *
 * Resource Aware ML *
 * * * * * * * * * * *
 * File:
 *   quicksort.raml
 *
 * Author:
 *   Jan Hoffmann (2009)
 *
 * Resource Bound:
 *   O(n^2)
 *
 * Description:
 *   Two implementations of the well known sorting algorithm quicksort.
 *   
 *   The function quicksort does not use a destructive pattern match
 *   and thus consumes quadratic heap-space and quadratic time.
 *
 *   quicksortD uses the destructive pattern matching to delete
 *   intermediate results.  This leads to a linear heap-space and
 *   quadratic time consumption.
 *)


quicksort : L(int) -> L(int)  
(* works out of the box as implemented in textbooks *)

quicksort l = let _=tick(1) in
              match l with
              | nil -> nil
              | (z::zs) -> let (xs,ys) = split (z,zs) in
                           append(quicksort xs, z::(quicksort ys));


split : (int,L(int)) -> (L(int),L(int))

split(pivot,l) = let _=tick(1) in
                  match l with
                    | nil     -> (nil,nil)
                    | (x::xs) -> let (ls,rs) = split (pivot,xs) in
                                 if x > pivot then (ls,x::rs) else (x::ls,rs);



append : (L(int),L(int)) -> L(int)

append(l,ys) = let _=tick(1) in
                match l with
                | nil -> ys
                | (x::xs) -> x::append(xs,ys);

main = ()