On Mon, Jan 24, 2005 at 01:02:44AM -0300, Horst von Brand wrote: > Matt Mackall <[EMAIL PROTECTED]> 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. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/