lkml.org 
[lkml]   [2005]   [Jan]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [patch 1/13] Qsort
Date
From
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.
--
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 majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 14:09    [W:0.192 / U:25.160 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site