diff options
Diffstat (limited to 'src/lib/libc/stdlib/qsort.3')
-rw-r--r-- | src/lib/libc/stdlib/qsort.3 | 12 |
1 files changed, 6 insertions, 6 deletions
diff --git a/src/lib/libc/stdlib/qsort.3 b/src/lib/libc/stdlib/qsort.3 index a65c5819d0..0a71824450 100644 --- a/src/lib/libc/stdlib/qsort.3 +++ b/src/lib/libc/stdlib/qsort.3 | |||
@@ -33,7 +33,7 @@ | |||
33 | .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | 33 | .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
34 | .\" SUCH DAMAGE. | 34 | .\" SUCH DAMAGE. |
35 | .\" | 35 | .\" |
36 | .\" $OpenBSD: qsort.3,v 1.2 1996/08/19 08:33:42 tholo Exp $ | 36 | .\" $OpenBSD: qsort.3,v 1.3 1999/02/27 21:56:00 deraadt Exp $ |
37 | .\" | 37 | .\" |
38 | .Dd June 4, 1993 | 38 | .Dd June 4, 1993 |
39 | .Dt QSORT 3 | 39 | .Dt QSORT 3 |
@@ -71,7 +71,7 @@ objects, the initial member of which is pointed to by | |||
71 | .Fa base . | 71 | .Fa base . |
72 | The size of each object is specified by | 72 | The size of each object is specified by |
73 | .Fa size . | 73 | .Fa size . |
74 | .Fn Mergesort | 74 | .Fn mergesort |
75 | behaves similarly, but | 75 | behaves similarly, but |
76 | .Em requires | 76 | .Em requires |
77 | that | 77 | that |
@@ -108,7 +108,7 @@ The | |||
108 | function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, | 108 | function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, |
109 | a variant of partition-exchange sorting; in particular, see D.E. Knuth's | 109 | a variant of partition-exchange sorting; in particular, see D.E. Knuth's |
110 | Algorithm Q. | 110 | Algorithm Q. |
111 | .Fn Qsort | 111 | .Fn qsort |
112 | takes O N lg N average time. | 112 | takes O N lg N average time. |
113 | This implementation uses median selection to avoid its | 113 | This implementation uses median selection to avoid its |
114 | O N**2 worst-case behavior. | 114 | O N**2 worst-case behavior. |
@@ -117,7 +117,7 @@ The | |||
117 | .Fn heapsort | 117 | .Fn heapsort |
118 | function is an implementation of J.W.J. William's ``heapsort'' algorithm, | 118 | function is an implementation of J.W.J. William's ``heapsort'' algorithm, |
119 | a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. | 119 | a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. |
120 | .Fn Heapsort | 120 | .Fn heapsort |
121 | takes O N lg N worst-case time. | 121 | takes O N lg N worst-case time. |
122 | Its | 122 | Its |
123 | .Em only | 123 | .Em only |
@@ -133,7 +133,7 @@ requires additional memory of size | |||
133 | .Fa nmemb * | 133 | .Fa nmemb * |
134 | .Fa size | 134 | .Fa size |
135 | bytes; it should be used only when space is not at a premium. | 135 | bytes; it should be used only when space is not at a premium. |
136 | .Fn Mergesort | 136 | .Fn mergesort |
137 | is optimized for data with pre-existing order; its worst case | 137 | is optimized for data with pre-existing order; its worst case |
138 | time is O N lg N; its best case is O N. | 138 | time is O N lg N; its best case is O N. |
139 | .Pp | 139 | .Pp |
@@ -175,7 +175,7 @@ argument to | |||
175 | is less than | 175 | is less than |
176 | .Dq "sizeof(void *) / 2" . | 176 | .Dq "sizeof(void *) / 2" . |
177 | .It Bq Er ENOMEM | 177 | .It Bq Er ENOMEM |
178 | .Fn Heapsort | 178 | .Fn heapsort |
179 | or | 179 | or |
180 | .Fn mergesort | 180 | .Fn mergesort |
181 | were unable to allocate memory. | 181 | were unable to allocate memory. |