Date: Mon, 18 Apr 2016 12:56:24 -0600 (MDT) From: Warren Block <wblock@wonkity.com> To: Hans Petter Selasky <hps@selasky.org> Cc: FreeBSD Current <freebsd-current@freebsd.org> Subject: Re: qsort() documentation Message-ID: <alpine.BSF.2.20.1604181250450.68720@wonkity.com> In-Reply-To: <5714C86A.8050204@selasky.org> References: <5714C86A.8050204@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, 18 Apr 2016, Hans Petter Selasky wrote: > Hi, > > Are there any objections adding the following as part of documenting our > kernel's qsort function? > > Index: sys/libkern/qsort.c > =================================================================== > --- sys/libkern/qsort.c (revision 298202) > +++ sys/libkern/qsort.c (working copy) > @@ -45,6 +45,10 @@ > > /* > * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". > + * > + * NOTE: This implementation of qsort() was designed to not have the "was designed to avoid the" > + * worst case complexity of N**2, as seen with the regular quick sort > + * functions as described by Wikipedia. > */ Why Wikipedia, specifically? There are a lot of places that describe quicksort. How about just Note: This implementation of qsort() is designed to avoid the worst-case complexity of N**2 that is often seen with standard versions.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?alpine.BSF.2.20.1604181250450.68720>