Re: [patch 1/13] Qsort

[Matt Mackall <mpm@selenic.com>]

On Mon, Jan 24, 2005 at 01:02:44AM -0300, Horst von Brand wrote:
> Matt Mackall <mpm@selenic.com> said:
> > On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:
> 
> [...]
> 
> > > -Andi (who thinks the glibc qsort is vast overkill for kernel purposes
> > > where there are only small data sets and it would be better to use a 
> > > simpler one optimized for code size)
> 
> > Mostly agreed. Except:
> > 
> > a) the glibc version is not actually all that optimized
> > b) it's nice that it's not recursive
> > c) the three-way median selection does help avoid worst-case O(n^2)
> > behavior, which might potentially be triggerable by users in places
> > like XFS where this is used
> 
> Shellsort is much simpler, and not much slower for small datasets. Plus no
> extra space for stacks.
> 
> > I'll probably whip up a simpler version tomorrow or Monday and do some
> > size/space benchmarking. I've been meaning to contribute a qsort for
> > doubly-linked lists I've got lying around as well.
> 
> Qsort is OK as long as you have direct access to each element. In case of
> lists, it is better to just use mergesort.

Qsort does not need to do random access. I posted an efficient
doubly-linked list version here four years ago:

template<class T>
void list<T>::qsort(iter l, iter r, cmpfunc *cmp, void *data)
{
        if(l==r) return;

        iter i(l), p(l);

        for(i++; i!=r; i++)
                if(cmp(*i, *l, data)<0)
                        i.swap(++p);

        l.swap(p);
        qsort(l, p, cmp, data);
        qsort(++p, r, cmp, data);
}

-- 
Mathematics is the supreme nostalgia of our time.