Libc-391.tar.gz

[apple/libc.git] / stdlib / FreeBSD / qsort.3

diff --git a/stdlib/FreeBSD/qsort.3 b/stdlib/FreeBSD/qsort.3
index c1a17e7851a62f2ba5a4565f0cc46e7c1031dbe8..5a901ce7bb0883b4dcb8abf90104a202673c4d8e 100644 (file)
--- a/stdlib/FreeBSD/qsort.3
+++ b/stdlib/FreeBSD/qsort.3
@@ -34,9 +34,9 @@
 .\" SUCH DAMAGE.
 .\"
 .\"     @(#)qsort.3    8.1 (Berkeley) 6/4/93
 .\" SUCH DAMAGE.
 .\"
 .\"     @(#)qsort.3    8.1 (Berkeley) 6/4/93

-.\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.13 2002/12/18 12:45:10 ru Exp $
+.\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.15 2004/07/02 23:52:12 ru Exp $

 .\"
 .\"

-.Dd September 7, 2002
+.Dd September 30, 2003

 .Dt QSORT 3
 .Os
 .Sh NAME
 .Dt QSORT 3
 .Os
 .Sh NAME


@@ -149,11 +149,13 @@ The
 .Fn qsort
 and
 .Fn qsort_r
 .Fn qsort
 and
 .Fn qsort_r

-functions are an implementation of C.A.R. Hoare's
+functions are an implementation of C.A.R.
+Hoare's

 .Dq quicksort
 algorithm,
 .Dq quicksort
 algorithm,

-a variant of partition-exchange sorting; in particular, see D.E. Knuth's
-Algorithm Q.
+a variant of partition-exchange sorting; in particular, see
+.An D.E. Knuth Ns 's
+.%T "Algorithm Q" .

 .Sy Quicksort
 takes O N lg N average time.
 This implementation uses median selection to avoid its
 .Sy Quicksort
 takes O N lg N average time.
 This implementation uses median selection to avoid its


@@ -161,10 +163,13 @@ O N**2 worst-case behavior.
 .Pp
 The
 .Fn heapsort
 .Pp
 The
 .Fn heapsort

-function is an implementation of J.W.J. William's
+function is an implementation of
+.An "J.W.J. William" Ns 's

 .Dq heapsort
 algorithm,
 .Dq heapsort
 algorithm,

-a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
+a variant of selection sorting; in particular, see
+.An "D.E. Knuth" Ns 's
+.%T "Algorithm H" .

 .Sy Heapsort
 takes O N lg N worst-case time.
 Its
 .Sy Heapsort
 takes O N lg N worst-case time.
 Its


@@ -263,16 +268,19 @@ This is no longer true.
 .%P pp. 114-123, 145-149
 .Re
 .Rs
 .%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
 .Re
 .Rs
 .%A Bentley, J.L.
 .%T "Optimistic Sorting and Information Theoretic Complexity"
 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 .%V January 1992
 .Re
 .Rs
 .%A Bentley, J.L.

+.%A McIlroy, M.D.

 .%T "Engineering a Sort Function"
 .%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
 The
 .Re
 .Sh STANDARDS
 The