1 files changed, 46 insertions, 47 deletions

diff --git a/src/lib/libc/stdlib/qsort.3 b/src/lib/libc/stdlib/qsort.3
index eb122cde12..92c75d5365 100644
--- a/src/lib/libc/stdlib/qsort.3
+++ b/src/lib/libc/stdlib/qsort.3
@@ -13,11 +13,7 @@
 .\" 2. Redistributions in binary form must reproduce the above copyright
 .\"    notice, this list of conditions and the following disclaimer in the
 .\"    documentation and/or other materials provided with the distribution.
-.\" 3. All advertising materials mentioning features or use of this software
-.\"    must display the following acknowledgement:
-.\"     This product includes software developed by the University of
-.\"     California, Berkeley and its contributors.
-.\" 4. Neither the name of the University nor the names of its contributors
+.\" 3. Neither the name of the University nor the names of its contributors
 .\"    may be used to endorse or promote products derived from this software
 .\"    without specific prior written permission.
 .\"
@@ -33,14 +29,15 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.\"     from: @(#)qsort.3       8.1 (Berkeley) 6/4/93
-.\"     $Id: qsort.3,v 1.1.1.1 1995/10/18 08:42:18 deraadt Exp $
+.\"     $OpenBSD: qsort.3,v 1.15 2007/05/31 19:19:31 jmc Exp $
 .\"
-.Dd June 4, 1993
+.Dd $Mdocdate: May 31 2007 $
 .Dt QSORT 3
 .Os
 .Sh NAME
-.Nm qsort, heapsort, mergesort
+.Nm qsort ,
+.Nm heapsort ,
+.Nm mergesort
 .Nd sort functions
 .Sh SYNOPSIS
 .Fd #include <stdlib.h>
@@ -72,7 +69,7 @@ objects, the initial member of which is pointed to by
 .Fa base .
 The size of each object is specified by
 .Fa size .
-.Fn Mergesort
+.Fn mergesort
 behaves similarly, but
 .Em requires
 that
@@ -106,51 +103,49 @@ is stable.
 .Pp
 The
 .Fn qsort
-function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
+function is an implementation of C.A.R. Hoare's
+.Dq quicksort
+algorithm,
 a variant of partition-exchange sorting; in particular, see D.E. Knuth's
 Algorithm Q.
-.Fn Qsort
+.Fn qsort
 takes O N lg N average time.
 This implementation uses median selection to avoid its
 O N**2 worst-case behavior.
 .Pp
 The
 .Fn heapsort
-function is an implementation of J.W.J. William's ``heapsort'' algorithm,
+function is an implementation of J.W.J. William's
+.Dq heapsort
+algorithm,
 a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
-.Fn Heapsort
+.Fn heapsort
 takes O N lg N worst-case time.
-Its
-.Em only
-advantage over
-.Fn qsort
-is that it uses almost no additional memory; while
-.Fn qsort
-does not allocate memory, it is implemented using recursion.
+This implementation of
+.Fn heapsort
+is implemented without recursive function calls.
 .Pp
 The function
 .Fn mergesort
 requires additional memory of size
 .Fa nmemb *
-.Fa size 
+.Fa size
 bytes; it should be used only when space is not at a premium.
-.Fn Mergesort
+.Fn mergesort
 is optimized for data with pre-existing order; its worst case
 time is O N lg N; its best case is O N.
 .Pp
 Normally,
 .Fn qsort
 is faster than
-.Fn mergesort
-is faster than
+.Fn mergesort ,
+which is faster than
 .Fn heapsort .
-Memory availability and pre-existing order in the data can make this
-untrue.
+Memory availability and pre-existing order in the data can make this untrue.
 .Sh RETURN VALUES
 The
 .Fn qsort
-function
-returns no value.
+function returns no value.
 .Pp
 Upon successful completion,
 .Fn heapsort
@@ -163,30 +158,25 @@ is set to indicate the error.
 .Sh ERRORS
 The
 .Fn heapsort
-function succeeds unless:
+and
+.Fn mergesort
+functions succeed unless:
 .Bl -tag -width Er
 .It Bq Er EINVAL
 The
 .Fa size
-argument is zero, or,
-the
+argument is zero, or the
 .Fa size
 argument to
 .Fn mergesort
 is less than
 .Dq "sizeof(void *) / 2" .
 .It Bq Er ENOMEM
-.Fn Heapsort
+.Fn heapsort
 or
 .Fn mergesort
 were unable to allocate memory.
 .El
-.Sh COMPATIBILITY
-Previous versions of
-.Fn qsort
-did not permit the comparison routine itself to call
-.Fn qsort 3 .
-This is no longer true.
 .Sh SEE ALSO
 .Xr sort 1 ,
 .Xr radixsort 3
@@ -204,7 +194,7 @@ This is no longer true.
 .%T "Heapsort"
 .%J "Communications of the ACM"
 .%V 7:1
-.%P pp. 347-348
+.%P pp. 347\-348
 .Re
 .Rs
 .%A Knuth, D.E.
@@ -212,23 +202,32 @@ This is no longer true.
 .%B "The Art of Computer Programming"
 .%V Vol. 3
 .%T "Sorting and Searching"
-.%P pp. 114-123, 145-149
+.%P pp. 114\-123, 145\-149
 .Re
 .Rs
-.%A Mcilroy, P.M.
+.%A McIlroy, P.M.
 .%T "Optimistic Sorting and Information Theoretic Complexity"
 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
-.%V January 1992
+.%P pp. 467\-464
+.%D January 1993
 .Re
 .Rs
 .%A Bentley, J.L.
+.%A McIlroy, M.D.
 .%T "Engineering a Sort Function"
-.%J "bentley@research.att.com"
-.%V January 1992
+.%J "Software \- Practice and Experience"
+.%V Vol. 23(11)
+.%P pp. 1249\-1265
+.%D November 1993
 .Re
 .Sh STANDARDS
+Previous versions of
+.Fn qsort
+did not permit the comparison routine itself to call
+.Fn qsort .
+This is no longer true.
+.Pp
 The
 .Fn qsort
-function
-conforms to
+function conforms to
 .St -ansiC .