/* Quicksort - sept 97 - by Sylvain Huet */ /* quicksort(l,f): fun [[u0 r1] fun [u0 u0] I] [u0 r1] function f(a,b)= 1 : a before b -1: a after b 0 : a equals b and must disappear */ fun conc(p,q)= if p==nil then q else (hd p)::conc (tl p) q;; fun dividelist(x,p,r1,r2,f)= if p==nil then [r1 r2] else let p->[a n] in let exec f with [a x] -> r in if r==0 then dividelist x n r1 r2 f else if r<0 then dividelist x n a::r1 r2 f else dividelist x n r1 a::r2 f;; fun quicksort(l,f)= if l==nil then nil else let l->[vl nl] in let dividelist vl nl nil nil f->[va na] in conc quicksort va f vl::quicksort na f;;