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