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.\" 3. 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$ 34.\" 35.Dd February 20, 2013 36.Dt QSORT 3 37.Os 38.Sh NAME 39.Nm qsort , qsort_b , qsort_r , heapsort , heapsort_b , mergesort, mergesort_b 40.Nd sort functions 41.Sh LIBRARY 42.Lb libc 43.Sh SYNOPSIS 44.In stdlib.h 45.Ft void 46.Fo qsort 47.Fa "void *base" 48.Fa "size_t nmemb" 49.Fa "size_t size" 50.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" 51.Fc 52.Ft void 53.Fo qsort_b 54.Fa "void *base" 55.Fa "size_t nmemb" 56.Fa "size_t size" 57.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" 58.Fc 59.Ft void 60.Fo qsort_r 61.Fa "void *base" 62.Fa "size_t nmemb" 63.Fa "size_t size" 64.Fa "void *thunk" 65.Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]" 66.Fc 67.Ft int 68.Fo heapsort 69.Fa "void *base" 70.Fa "size_t nmemb" 71.Fa "size_t size" 72.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" 73.Fc 74.Ft int 75.Fo heapsort_b 76.Fa "void *base" 77.Fa "size_t nmemb" 78.Fa "size_t size" 79.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" 80.Fc 81.Ft int 82.Fo mergesort 83.Fa "void *base" 84.Fa "size_t nmemb" 85.Fa "size_t size" 86.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" 87.Fc 88.Ft int 89.Fo mergesort_b 90.Fa "void *base" 91.Fa "size_t nmemb" 92.Fa "size_t size" 93.Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]" 94.Fc 95.Sh DESCRIPTION 96The 97.Fn qsort 98function is a modified partition-exchange sort, or quicksort. 99The 100.Fn heapsort 101function is a modified selection sort. 102The 103.Fn mergesort 104function is a modified merge sort with exponential search 105intended for sorting data with pre-existing order. 106.Pp 107The 108.Fn qsort 109and 110.Fn heapsort 111functions sort an array of 112.Fa nmemb 113objects, the initial member of which is pointed to by 114.Fa base . 115The size of each object is specified by 116.Fa size . 117The 118.Fn mergesort 119function 120behaves similarly, but 121.Em requires 122that 123.Fa size 124be greater than 125.Dq "sizeof(void *) / 2" . 126.Pp 127The contents of the array 128.Fa base 129are sorted in ascending order according to 130a comparison function pointed to by 131.Fa compar , 132which requires two arguments pointing to the objects being 133compared. 134.Pp 135The comparison function must return an integer less than, equal to, or 136greater than zero if the first argument is considered to be respectively 137less than, equal to, or greater than the second. 138.Pp 139The 140.Fn qsort_r 141function behaves identically to 142.Fn qsort , 143except that it takes an additional argument, 144.Fa thunk , 145which is passed unchanged as the first argument to function pointed to 146.Fa compar . 147This allows the comparison function to access additional 148data without using global variables, and thus 149.Fn qsort_r 150is suitable for use in functions which must be reentrant. 151The 152.Fn qsort_b 153function behaves identically to 154.Fn qsort , 155except that it takes a block, rather than a function pointer. 156.Pp 157The algorithms implemented by 158.Fn qsort , 159.Fn qsort_r , 160and 161.Fn heapsort 162are 163.Em not 164stable, that is, if two members compare as equal, their order in 165the sorted array is undefined. 166The 167.Fn heapsort_b 168function behaves identically to 169.Fn heapsort , 170except that it takes a block, rather than a function pointer. 171The 172.Fn mergesort 173algorithm is stable. 174The 175.Fn mergesort_b 176function behaves identically to 177.Fn mergesort , 178except that it takes a block, rather than a function pointer. 179.Pp 180The 181.Fn qsort 182and 183.Fn qsort_r 184functions are an implementation of C.A.R. 185Hoare's 186.Dq quicksort 187algorithm, 188a variant of partition-exchange sorting; in particular, see 189.An D.E. Knuth Ns 's 190.%T "Algorithm Q" . 191.Sy Quicksort 192takes O N lg N average time. 193This implementation uses median selection to avoid its 194O N**2 worst-case behavior. 195.Pp 196The 197.Fn heapsort 198function is an implementation of 199.An "J.W.J. William" Ns 's 200.Dq heapsort 201algorithm, 202a variant of selection sorting; in particular, see 203.An "D.E. Knuth" Ns 's 204.%T "Algorithm H" . 205.Sy Heapsort 206takes O N lg N worst-case time. 207Its 208.Em only 209advantage over 210.Fn qsort 211is that it uses almost no additional memory; while 212.Fn qsort 213does not allocate memory, it is implemented using recursion. 214.Pp 215The function 216.Fn mergesort 217requires additional memory of size 218.Fa nmemb * 219.Fa size 220bytes; it should be used only when space is not at a premium. 221The 222.Fn mergesort 223function 224is optimized for data with pre-existing order; its worst case 225time is O N lg N; its best case is O N. 226.Pp 227Normally, 228.Fn qsort 229is faster than 230.Fn mergesort 231is faster than 232.Fn heapsort . 233Memory availability and pre-existing order in the data can make this 234untrue. 235.Sh RETURN VALUES 236The 237.Fn qsort 238and 239.Fn qsort_r 240functions 241return no value. 242.Pp 243.Rv -std heapsort mergesort 244.Sh EXAMPLES 245A sample program that sorts an array of 246.Vt int 247values in place using 248.Fn qsort , 249and then prints the sorted array to standard output is: 250.Bd -literal 251#include <stdio.h> 252#include <stdlib.h> 253 254/* 255 * Custom comparison function that compares 'int' values through pointers 256 * passed by qsort(3). 257 */ 258static int 259int_compare(const void *p1, const void *p2) 260{ 261 int left = *(const int *)p1; 262 int right = *(const int *)p2; 263 264 return ((left > right) - (left < right)); 265} 266 267/* 268 * Sort an array of 'int' values and print it to standard output. 269 */ 270int 271main(void) 272{ 273 int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 }; 274 size_t array_size = sizeof(int_array) / sizeof(int_array[0]); 275 size_t k; 276 277 qsort(&int_array, array_size, sizeof(int_array[0]), int_compare); 278 for (k = 0; k < array_size; k++) 279 printf(" %d", int_array[k]); 280 puts(""); 281 return (EXIT_SUCCESS); 282} 283.Ed 284.Sh COMPATIBILITY 285Previous versions of 286.Fn qsort 287did not permit the comparison routine itself to call 288.Fn qsort 3 . 289This is no longer true. 290.Sh ERRORS 291The 292.Fn heapsort 293and 294.Fn mergesort 295functions succeed unless: 296.Bl -tag -width Er 297.It Bq Er EINVAL 298The 299.Fa size 300argument is zero, or, 301the 302.Fa size 303argument to 304.Fn mergesort 305is less than 306.Dq "sizeof(void *) / 2" . 307.It Bq Er ENOMEM 308The 309.Fn heapsort 310or 311.Fn mergesort 312functions 313were unable to allocate memory. 314.El 315.Sh SEE ALSO 316.Xr sort 1 , 317.Xr radixsort 3 318.Rs 319.%A Hoare, C.A.R. 320.%D 1962 321.%T "Quicksort" 322.%J "The Computer Journal" 323.%V 5:1 324.%P pp. 10-15 325.Re 326.Rs 327.%A Williams, J.W.J 328.%D 1964 329.%T "Heapsort" 330.%J "Communications of the ACM" 331.%V 7:1 332.%P pp. 347-348 333.Re 334.Rs 335.%A Knuth, D.E. 336.%D 1968 337.%B "The Art of Computer Programming" 338.%V Vol. 3 339.%T "Sorting and Searching" 340.%P pp. 114-123, 145-149 341.Re 342.Rs 343.%A McIlroy, P.M. 344.%T "Optimistic Sorting and Information Theoretic Complexity" 345.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" 346.%V January 1992 347.Re 348.Rs 349.%A Bentley, J.L. 350.%A McIlroy, M.D. 351.%T "Engineering a Sort Function" 352.%J "Software--Practice and Experience" 353.%V Vol. 23(11) 354.%P pp. 1249-1265 355.%D November\ 1993 356.Re 357.Sh STANDARDS 358The 359.Fn qsort 360function 361conforms to 362.St -isoC . 363.Sh HISTORY 364The variants of these functions that take blocks as arguments first appeared in 365Mac OS X. 366This implementation was created by David Chisnall. 367