1.\"	$NetBSD: qsort.3,v 1.15 2025/03/02 16:35:41 riastradh Exp $
2.\"
3.\" Copyright (c) 1990, 1991, 1993
4.\"	The Regents of the University of California.  All rights reserved.
5.\"
6.\" This code is derived from software contributed to Berkeley by
7.\" the American National Standards Committee X3, on Information
8.\" Processing Systems.
9.\"
10.\" Redistribution and use in source and binary forms, with or without
11.\" modification, are permitted provided that the following conditions
12.\" are met:
13.\" 1. Redistributions of source code must retain the above copyright
14.\"    notice, this list of conditions and the following disclaimer.
15.\" 2. Redistributions in binary form must reproduce the above copyright
16.\"    notice, this list of conditions and the following disclaimer in the
17.\"    documentation and/or other materials provided with the distribution.
18.\" 3. Neither the name of the University nor the names of its contributors
19.\"    may be used to endorse or promote products derived from this software
20.\"    without specific prior written permission.
21.\"
22.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32.\" SUCH DAMAGE.
33.\"
34.\"     from: @(#)qsort.3	8.1 (Berkeley) 6/4/93
35.\"
36.Dd June 4, 1993
37.Dt QSORT 3
38.Os
39.Sh NAME
40.Nm qsort ,
41.Nm heapsort ,
42.Nm mergesort
43.Nd sort functions
44.Sh LIBRARY
45.Lb libc
46.Sh SYNOPSIS
47.In stdlib.h
48.Ft void
49.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
50.Ft void
51.Fn qsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
52.Ft int
53.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
54.Ft int
55.Fn heapsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
56.Ft int
57.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
58.Ft int
59.Fn mergesort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
60.Sh DESCRIPTION
61The
62.Fn qsort
63function is a modified partition-exchange sort, or quicksort.
64The
65.Fn heapsort
66function is a modified selection sort.
67The
68.Fn mergesort
69function is a modified merge sort with exponential search
70intended for sorting data with pre-existing order.
71.Pp
72The
73.Fn qsort
74and
75.Fn heapsort
76functions sort an array of
77.Fa nmemb
78objects, the initial member of which is pointed to by
79.Fa base .
80The size of each object is specified by
81.Fa size .
82.Fn mergesort
83behaves similarly, but
84.Em requires
85that
86.Fa size
87be greater than
88.Dq "sizeof(void *) / 2" .
89.Pp
90The contents of the array
91.Fa base
92are sorted in ascending order according to
93a comparison function pointed to by
94.Fa compar ,
95which requires two arguments pointing to the objects being
96compared.
97.Pp
98The comparison function must return an integer less than, equal to, or
99greater than zero if the first argument is considered to be respectively
100less than, equal to, or greater than the second.
101.Pp
102The functions
103.Fn qsort
104and
105.Fn heapsort
106are
107.Em not
108stable, that is, if two members compare as equal, their order in
109the sorted array is undefined.
110The function
111.Fn mergesort
112is stable.
113.Pp
114The
115.Fn qsort_r ,
116.Fn heapsort_r ,
117and
118.Fn mergesort_r
119functions pass an additional cookie argument through to the comparison
120function.
121.Pp
122The
123.Fn qsort
124function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
125a variant of partition-exchange sorting; in particular, see D.E. Knuth's
126Algorithm Q.
127.Fn qsort
128takes O N lg N average time.
129This implementation uses median selection to avoid its
130O N**2 worst-case behavior.
131.Pp
132The
133.Fn heapsort
134function is an implementation of J.W.J. William's ``heapsort'' algorithm,
135a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
136.Fn heapsort
137takes O N lg N worst-case time.
138Its
139.Em only
140advantage over
141.Fn qsort
142is that it uses almost no additional memory; while
143.Fn qsort
144does not allocate memory, it is implemented using recursion.
145.Pp
146The function
147.Fn mergesort
148requires additional memory of size
149.Fa nmemb *
150.Fa size
151bytes; it should be used only when space is not at a premium.
152.Fn mergesort
153is optimized for data with pre-existing order; its worst case
154time is O N lg N; its best case is O N.
155.Pp
156Normally,
157.Fn qsort
158is faster than
159.Fn mergesort
160is faster than
161.Fn heapsort .
162Memory availability and pre-existing order in the data can make this
163untrue.
164.Sh RETURN VALUES
165The
166.Fn qsort
167function
168returns no value.
169.Pp
170Upon successful completion,
171.Fn heapsort
172and
173.Fn mergesort
174return 0.
175Otherwise, they return \-1 and the global variable
176.Va errno
177is set to indicate the error.
178.Sh COMPATIBILITY
179Previous versions of
180.Fn qsort
181did not permit the comparison routine itself to call
182.Fn qsort .
183This is no longer true.
184.Sh ERRORS
185The
186.Fn heapsort
187function succeeds unless:
188.Bl -tag -width Er
189.It Bq Er EINVAL
190The
191.Fa size
192argument is zero, or,
193the
194.Fa size
195argument to
196.Fn mergesort
197is less than
198.Dq "sizeof(void *) / 2" .
199.It Bq Er ENOMEM
200.Fn heapsort
201or
202.Fn mergesort
203were unable to allocate memory.
204.El
205.Sh SEE ALSO
206.Xr sort 1 ,
207.Xr radixsort 3
208.Rs
209.%A Hoare, C.A.R.
210.%D 1962
211.%T "Quicksort"
212.%J "The Computer Journal"
213.%V 5:1
214.%P pp. 10-15
215.Re
216.Rs
217.%A Williams, J.W.J
218.%D 1964
219.%T "Heapsort"
220.%J "Communications of the ACM"
221.%V 7:1
222.%P pp. 347-348
223.Re
224.Rs
225.%A Knuth, D.E.
226.%D 1968
227.%B "The Art of Computer Programming"
228.%V Vol. 3
229.%T "Sorting and Searching"
230.%P pp. 114-123, 145-149
231.Re
232.Rs
233.%A McIlroy, P.M.
234.%D 1993
235.%T "Optimistic Sorting and Information Theoretic Complexity"
236.%J "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
237.%P pp. 467-474
238.Re
239.Rs
240.%A Bentley, J.L. and McIlroy, M.D.
241.%D 1993
242.%T "Engineering a Sort Function"
243.%J "Software-Practice and Experience"
244.%V Vol. 23
245.%P pp. 1249-1265
246.Re
247.Sh STANDARDS
248The
249.Fn qsort
250function conforms to
251.St -ansiC .
252.Pp
253The
254.Fn qsort_r
255function conforms to
256.St -p1003.1-2024 .
257