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