1  .\" Copyright (c) 1990, 1991, 1993
  2  .\"	The Regents of the University of California.  All rights reserved.
  3  .\"
  4  .\" This code is derived from software contributed to Berkeley by
  5  .\" the American National Standards Committee X3, on Information
  6  .\" Processing Systems.
  7  .\"
  8  .\" Redistribution and use in source and binary forms, with or without
  9  .\" modification, are permitted provided that the following conditions
 10  .\" are met:
 11  .\" 1. Redistributions of source code must retain the above copyright
 12  .\"    notice, this list of conditions and the following disclaimer.
 13  .\" 2. Redistributions in binary form must reproduce the above copyright
 14  .\"    notice, this list of conditions and the following disclaimer in the
 15  .\"    documentation and/or other materials provided with the distribution.
 16  .\" 4. Neither the name of the University nor the names of its contributors
 17  .\"    may be used to endorse or promote products derived from this software
 18  .\"    without specific prior written permission.
 19  .\"
 20  .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 21  .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 22  .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 23  .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 24  .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 25  .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 26  .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 27  .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 28  .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 29  .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 30  .\" SUCH DAMAGE.
 31  .\"
 32  .\"     @(#)qsort.3	8.1 (Berkeley) 6/4/93
 33  .\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.17 2007/01/09 00:28:10 imp Exp $
 34  .\"
 35  .Dd September 30, 2003
 36  .Dt QSORT 3
 37  .Os
 38  .Sh NAME
 39  .Nm heapsort ,
 40  #ifdef UNIFDEF_BLOCKS
 41  .Nm heapsort_b ,
 42  #endif
 43  .Nm mergesort ,
 44  #ifdef UNIFDEF_BLOCKS
 45  .Nm mergesort_b ,
 46  #endif
 47  .Nm qsort ,
 48  #ifdef UNIFDEF_BLOCKS
 49  .Nm qsort_b ,
 50  #endif
 51  .Nm qsort_r
 52  .Nd sort functions
 53  .Sh SYNOPSIS
 54  .In stdlib.h
 55  .Ft int
 56  .Fo heapsort
 57  .Fa "void *base"
 58  .Fa "size_t nel"
 59  .Fa "size_t width"
 60  .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 61  .Fc
 62  #ifdef UNIFDEF_BLOCKS
 63  .Ft int
 64  .Fo heapsort_b
 65  .Fa "void *base"
 66  .Fa "size_t nel"
 67  .Fa "size_t width"
 68  .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 69  .Fc
 70  #endif
 71  .Ft int
 72  .Fo mergesort
 73  .Fa "void *base"
 74  .Fa "size_t nel"
 75  .Fa "size_t width"
 76  .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 77  .Fc
 78  #ifdef UNIFDEF_BLOCKS
 79  .Ft int
 80  .Fo mergesort_b
 81  .Fa "void *base"
 82  .Fa "size_t nel"
 83  .Fa "size_t width"
 84  .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 85  .Fc
 86  #endif
 87  .Ft void
 88  .Fo qsort
 89  .Fa "void *base"
 90  .Fa "size_t nel"
 91  .Fa "size_t width"
 92  .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 93  .Fc
 94  #ifdef UNIFDEF_BLOCKS
 95  .Ft void
 96  .Fo qsort_b
 97  .Fa "void *base"
 98  .Fa "size_t nel"
 99  .Fa "size_t width"
100  .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
101  .Fc
102  #endif
103  .Ft void
104  .Fo qsort_r
105  .Fa "void *base"
106  .Fa "size_t nel"
107  .Fa "size_t width"
108  .Fa "void *thunk"
109  .Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
110  .Fc
111  .Sh DESCRIPTION
112  The
113  .Fn qsort
114  function is a modified partition-exchange sort, or quicksort.
115  The
116  .Fn heapsort
117  function is a modified selection sort.
118  The
119  .Fn mergesort
120  function is a modified merge sort with exponential search,
121  intended for sorting data with pre-existing order.
122  .Pp
123  The
124  .Fn qsort
125  and
126  .Fn heapsort
127  functions sort an array of
128  .Fa nel
129  objects, the initial member of which is pointed to by
130  .Fa base .
131  The size of each object is specified by
132  .Fa width .
133  The
134  .Fn mergesort
135  function
136  behaves similarly, but
137  .Em requires
138  that
139  .Fa width
140  be greater than or equal to
141  .Dq "sizeof(void *) / 2" .
142  .Pp
143  The contents of the array
144  .Fa base
145  are sorted in ascending order according to
146  a comparison function pointed to by
147  .Fa compar ,
148  which requires two arguments pointing to the objects being
149  compared.
150  .Pp
151  The comparison function must return an integer less than, equal to, or
152  greater than zero if the first argument is considered to be respectively
153  less than, equal to, or greater than the second.
154  .Pp
155  The
156  .Fn qsort_r
157  function behaves identically to
158  .Fn qsort ,
159  except that it takes an additional argument,
160  .Fa thunk ,
161  which is passed unchanged as the first argument to function pointed to
162  .Fa compar .
163  This allows the comparison function to access additional
164  data without using global variables, and thus
165  .Fn qsort_r
166  is suitable for use in functions which must be reentrant.
167  .Pp
168  The algorithms implemented by
169  .Fn qsort ,
170  .Fn qsort_r ,
171  and
172  .Fn heapsort
173  are
174  .Em not
175  stable; that is, if two members compare as equal, their order in
176  the sorted array is undefined.
177  The
178  .Fn mergesort
179  algorithm is stable.
180  .Pp
181  The
182  .Fn qsort
183  and
184  .Fn qsort_r
185  functions are an implementation of C.A.R.
186  Hoare's
187  .Dq quicksort
188  algorithm,
189  a variant of partition-exchange sorting; in particular, see
190  .An D.E. Knuth Ns 's
191  .%T "Algorithm Q" .
192  .Sy Quicksort
193  takes O N lg N average time.
194  This implementation uses median selection to avoid its
195  O N**2 worst-case behavior.
196  .Pp
197  The
198  .Fn heapsort
199  function is an implementation of
200  .An "J.W.J. William" Ns 's
201  .Dq heapsort
202  algorithm,
203  a variant of selection sorting; in particular, see
204  .An "D.E. Knuth" Ns 's
205  .%T "Algorithm H" .
206  .Sy Heapsort
207  takes O N lg N worst-case time.
208  Its
209  .Em only
210  advantage over
211  .Fn qsort
212  is that it uses almost no additional memory; while
213  .Fn qsort
214  does not allocate memory, it is implemented using recursion.
215  .Pp
216  The function
217  .Fn mergesort
218  requires additional memory of size
219  .Fa nel *
220  .Fa width
221  bytes; it should be used only when space is not at a premium.
222  The
223  .Fn mergesort
224  function
225  is optimized for data with pre-existing order; its worst case
226  time is O N lg N; its best case is O N.
227  .Pp
228  Normally,
229  .Fn qsort
230  is faster than
231  .Fn mergesort
232  which is faster than
233  .Fn heapsort .
234  Memory availability and pre-existing order in the data can make this
235  untrue.
236  #ifdef UNIFDEF_BLOCKS
237  .Pp
238  The
239  .Fn heapsort_b ,
240  .Fn mergesort_b ,
241  and
242  .Fn qsort_b
243  routines are like the corresponding routines without the _b suffix, expect
244  that the
245  .Fa compar
246  callback is a block pointer instead of a function pointer.
247  #endif
248  .Sh RETURN VALUES
249  The
250  #ifdef UNIFDEF_BLOCKS
251  .Fn qsort ,
252  .Fn qsort_b
253  #else
254  .Fn qsort
255  #endif
256  and
257  .Fn qsort_r
258  functions
259  return no value.
260  .Pp
261  #ifdef UNIFDEF_BLOCKS
262  .ds HEAPSORT_B heapsort_b
263  .ds MERGESORT_B mergesort_b
264  #endif
265  .Rv -std heapsort \*[HEAPSORT_B] mergesort \*[MERGESORT_B]
266  .Sh COMPATIBILITY
267  Previous versions of
268  .Fn qsort
269  did not permit the comparison routine itself to call
270  .Fn qsort 3 .
271  This is no longer true.
272  .Sh ERRORS
273  The
274  #ifdef UNIFDEF_BLOCKS
275  .Fn heapsort ,
276  .Fn heapsort_b ,
277  .Fn mergesort ,
278  and
279  .Fn mergesort_b
280  #else
281  .Fn heapsort
282  and
283  .Fn mergesort
284  #endif
285  functions succeed unless:
286  .Bl -tag -width Er
287  .It Bq Er EINVAL
288  The
289  .Fa width
290  argument is zero, or,
291  the
292  .Fa width
293  argument to
294  .Fn mergesort
295  #ifdef UNIFDEF_BLOCKS
296  or
297  .Fn mergesort_b
298  #endif
299  is less than
300  .Dq "sizeof(void *) / 2" .
301  .It Bq Er ENOMEM
302  The
303  #ifdef UNIFDEF_BLOCKS
304  .Fn heapsort ,
305  .Fn heapsort_b ,
306  .Fn mergesort ,
307  or
308  .Fn mergesort_b
309  #else
310  .Fn heapsort
311  or
312  .Fn mergesort
313  #endif
314  functions
315  were unable to allocate memory.
316  .El
317  .Sh SEE ALSO
318  .Xr sort 1 ,
319  .Xr radixsort 3
320  .Rs
321  .%A Hoare, C.A.R.
322  .%D 1962
323  .%T "Quicksort"
324  .%J "The Computer Journal"
325  .%V 5:1
326  .%P pp. 10-15
327  .Re
328  .Rs
329  .%A Williams, J.W.J
330  .%D 1964
331  .%T "Heapsort"
332  .%J "Communications of the ACM"
333  .%V 7:1
334  .%P pp. 347-348
335  .Re
336  .Rs
337  .%A Knuth, D.E.
338  .%D 1968
339  .%B "The Art of Computer Programming"
340  .%V Vol. 3
341  .%T "Sorting and Searching"
342  .%P pp. 114-123, 145-149
343  .Re
344  .Rs
345  .%A McIlroy, P.M.
346  .%T "Optimistic Sorting and Information Theoretic Complexity"
347  .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
348  .%V January 1992
349  .Re
350  .Rs
351  .%A Bentley, J.L.
352  .%A McIlroy, M.D.
353  .%T "Engineering a Sort Function"
354  .%J "Software--Practice and Experience"
355  .%V Vol. 23(11)
356  .%P pp. 1249-1265
357  .%D November\ 1993
358  .Re
359  .Sh STANDARDS
360  The
361  .Fn qsort
362  function
363  conforms to
364  .St -isoC .