[lkml]   [2005]   [Jan]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [patch 1/13] Qsort
    On Mon, Jan 24, 2005 at 01:02:44AM -0300, Horst von Brand wrote:
    > Matt Mackall <> 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)

    qsort(l, p, cmp, data);
    qsort(++p, r, cmp, data);

    Mathematics is the supreme nostalgia of our time.
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 14:09    [W:0.028 / U:1.692 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site