Thomas Hartman tphyahoo at gmail.com
Fri Apr 13 05:53:47 EDT 2007

```Trying to understand this better I also came across

where apfulmus gives an implementation of mergesort, which he claims

"runs in O(n) time instead of the expected O(n log n)"

Does that mean you can have the k minima in O(n) time, where n is
length of list, which would seem to be an improvement?

mergesort []  = []
mergesort xs  = foldtree1 merge \$ map return xs

foldtree1 f [x] = x
foldtree1 f xs  = foldtree1 f \$ pairs xs
where
pairs []        = []
pairs [x]       = [x]
pairs (x:x':xs) = f x x' : pairs xs

merge []     ys     = ys
merge xs     []     = xs
merge (x:xs) (y:ys) =
if x <= y then x:merge xs (y:ys) else y:merge (x:xs) ys

2007/4/13, Thomas Hartman <tphyahoo at gmail.com>:
> And for reference, here is again stefan's "stable" quicksort from his
> earlier post.
>
> "
> sort [] = []
> sort l@(x:_) = filter (<x) l ++ filter (==x) l ++ filter (>x) l
>
> (A stable quicksort, btw)
> "
>
> This is the code whose legitimacy I am requesting confirmation of.
>
> 2007/4/13, Thomas Hartman <tphyahoo at gmail.com>:
> > > > You may be missing a few recursive calls there :-)
> > >
> > > Indeed.
> >
> > I'm confused.
> >
> > Is this a legitimate stable quicksort, or not? (My guess is, it is
> > indeed legit as written.)
> >
> > This was also the first I have heard of stability as a sort property.
> >
> > http://perldoc.perl.org/sort.html may shed some light on this...
> >
> > "A stable sort means that for records that compare equal, the original
> > input ordering is preserved. Mergesort is stable, quicksort is not. "
> >
> > Is this description a fair characterization of stability for the
> > current discussion?
> >
> > I'm a bit confused but if I understand correctly sort from the prelude
> > is non stable quicksort, which has O(k n^2) as the worst case, whereas
> > stable quicksort has O( k* log n + n).
> >
> > non-stable quicksort is just sort from the prelude:
> >
> > qsort []     = []
> > qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
> >
> > If any in the above was incorrect, please holler.
> >
> > 2007/4/12, Stefan O'Rear <stefanor at cox.net>:
> > > On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote:
> > > > On 4/11/07, Stefan O'Rear <stefanor at cox.net> wrote:
> > > > >
> > > > >If you want to be really explicit about it, here is a sort that will
> > > > >work:
> > > > >
> > > > >sort [] = []
> > > > >sort l@(x:_) = filter (<x) l ++ filter (==x) l ++ filter (>x) l
> > > > >
> > > > >(A stable quicksort, btw)
> > > >
> > > > You may be missing a few recursive calls there :-)
> > >
> > > Indeed.
> > >
> > > Stefan
> > > _______________________________________________
> > > Haskell-Cafe mailing list