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. -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513 - 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/
