summaryrefslogtreecommitdiff
path: root/lib/libc/stdlib/qsort.3
diff options
context:
space:
mode:
authormycroft <mycroft@NetBSD.org>1994-06-16 05:26:34 +0000
committermycroft <mycroft@NetBSD.org>1994-06-16 05:26:34 +0000
commit2f86deea8e90ce29c02220c4dddefd9ab125ba4e (patch)
tree6fb7f4522f6891946fade372d17bd024bcd4f7b7 /lib/libc/stdlib/qsort.3
parent2c1d50080bc3867464bbfd9cacf68000d5c5a394 (diff)
Add RCS ids.
Diffstat (limited to 'lib/libc/stdlib/qsort.3')
-rw-r--r--lib/libc/stdlib/qsort.393
1 files changed, 79 insertions, 14 deletions
diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3
index bbea5307c49..7983379b0b7 100644
--- a/lib/libc/stdlib/qsort.3
+++ b/lib/libc/stdlib/qsort.3
@@ -1,5 +1,5 @@
-.\" Copyright (c) 1990, 1991 The Regents of the University of California.
-.\" All rights reserved.
+.\" Copyright (c) 1990, 1991, 1993
+.\" The Regents of the University of California. All rights reserved.
.\"
.\" This code is derived from software contributed to Berkeley by
.\" the American National Standards Committee X3, on Information
@@ -33,14 +33,14 @@
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
-.\" from: @(#)qsort.3 6.7 (Berkeley) 6/29/91
-.\" $Id: qsort.3,v 1.2 1993/08/01 07:44:22 mycroft Exp $
+.\" from: @(#)qsort.3 8.1 (Berkeley) 6/4/93
+.\" $Id: qsort.3,v 1.3 1994/06/16 05:26:38 mycroft Exp $
.\"
-.Dd June 29, 1991
+.Dd June 4, 1993
.Dt QSORT 3
.Os
.Sh NAME
-.Nm qsort, heapsort
+.Nm qsort, heapsort, mergesort
.Nd sort functions
.Sh SYNOPSIS
.Fd #include <stdlib.h>
@@ -48,6 +48,8 @@
.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
.Ft int
.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
+.Ft int
+.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
.Sh DESCRIPTION
The
.Fn qsort
@@ -55,6 +57,10 @@ function is a modified partition-exchange sort, or quicksort.
The
.Fn heapsort
function is a modified selection sort.
+The
+.Fn mergesort
+function is a modified merge sort with exponential search
+intended for sorting data with pre-existing order.
.Pp
The
.Fn qsort
@@ -66,11 +72,20 @@ objects, the initial member of which is pointed to by
.Fa base .
The size of each object is specified by
.Fa size .
+.Fn Mergesort
+behaves similarly, but
+.Em requires
+that
+.Fa size
+be greater than
+.Dq "sizeof(void *) / 2" .
.Pp
-The contents of the array are sorted in ascending order according to
+The contents of the array
+.Fa base
+are sorted in ascending order according to
a comparison function pointed to by
.Fa compar ,
-which is called with two arguments that point to the objects being
+which requires two arguments pointing to the objects being
compared.
.Pp
The comparison function must return an integer less than, equal to, or
@@ -85,6 +100,9 @@ are
.Em not
stable, that is, if two members compare as equal, their order in
the sorted array is undefined.
+The function
+.Fn mergesort
+is stable.
.Pp
The
.Fn qsort
@@ -93,7 +111,7 @@ a variant of partition-exchange sorting; in particular, see D.E. Knuth's
Algorithm Q.
.Fn Qsort
takes O N lg N average time.
-This implementation uses median selection to avoid the traditional
+This implementation uses median selection to avoid its
O N**2 worst-case behavior.
.Pp
The
@@ -106,7 +124,28 @@ Its
.Em only
advantage over
.Fn qsort
-is that it uses no additional memory.
+is that it uses almost no additional memory; while
+.Fn qsort
+does not allocate memory, it is implemented using recursion.
+.Pp
+The function
+.Fn mergesort
+requires additional memory of size
+.Fa nmemb *
+.Fa size
+bytes; it should be used only when space is not at a premium.
+.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 heapsort .
+Memory availability and pre-existing order in the data can make this
+untrue.
.Sh RETURN VALUES
The
.Fn qsort
@@ -115,8 +154,10 @@ returns no value.
.Pp
Upon successful completion,
.Fn heapsort
-returns 0.
-Otherwise, it returns \-1 and the global variable
+and
+.Fn mergesort
+return 0.
+Otherwise, they return \-1 and the global variable
.Va errno
is set to indicate the error.
.Sh ERRORS
@@ -127,11 +168,23 @@ function succeeds unless:
.It Bq Er EINVAL
The
.Fa size
-argument is zero.
+argument is zero, or,
+the
+.Fa size
+argument to
+.Fn mergesort
+is less than
+.Dq "sizeof(void *) / 2" .
+.It Bq Er ENOMEM
+.Fn Heapsort
+or
+.Fn mergesort
+were unable to allocate memory.
+.El
.Sh COMPATIBILITY
Previous versions of
.Fn qsort
-did not permit the comparison routine to itself call
+did not permit the comparison routine itself to call
.Fn qsort 3 .
This is no longer true.
.Sh SEE ALSO
@@ -161,6 +214,18 @@ This is no longer true.
.%T "Sorting and Searching"
.%P pp. 114-123, 145-149
.Re
+.Rs
+.%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 "Engineering a Sort Function"
+.%J "bentley@research.att.com"
+.%V January 1992
+.Re
.Sh STANDARDS
The
.Fn qsort