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 January 20, 2020 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.Fd #define __STDC_WANT_LIB_EXT1__ 1 102.Ft errno_t 103.Fo qsort_s 104.Fa "void *base" 105.Fa "rsize_t nmemb" 106.Fa "rsize_t size" 107.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *, void *\*[rp]" 108.Fa "void *thunk" 109.Fc 110.Sh DESCRIPTION 111The 112.Fn qsort 113function is a modified partition-exchange sort, or quicksort. 114The 115.Fn heapsort 116function is a modified selection sort. 117The 118.Fn mergesort 119function is a modified merge sort with exponential search 120intended for sorting data with pre-existing order. 121.Pp 122The 123.Fn qsort 124and 125.Fn heapsort 126functions sort an array of 127.Fa nmemb 128objects, the initial member of which is pointed to by 129.Fa base . 130The size of each object is specified by 131.Fa size . 132The 133.Fn mergesort 134function 135behaves similarly, but 136.Em requires 137that 138.Fa size 139be greater than 140.Dq "sizeof(void *) / 2" . 141.Pp 142The contents of the array 143.Fa base 144are sorted in ascending order according to 145a comparison function pointed to by 146.Fa compar , 147which requires two arguments pointing to the objects being 148compared. 149.Pp 150The comparison function must return an integer less than, equal to, or 151greater than zero if the first argument is considered to be respectively 152less than, equal to, or greater than the second. 153.Pp 154The 155.Fn qsort_r 156function behaves identically to 157.Fn qsort , 158except that it takes an additional argument, 159.Fa thunk , 160which is passed unchanged as the first argument to function pointed to 161.Fa compar . 162This allows the comparison function to access additional 163data without using global variables, and thus 164.Fn qsort_r 165is suitable for use in functions which must be reentrant. 166The 167.Fn qsort_b 168function behaves identically to 169.Fn qsort , 170except that it takes a block, rather than a function pointer. 171.Pp 172The algorithms implemented by 173.Fn qsort , 174.Fn qsort_r , 175and 176.Fn heapsort 177are 178.Em not 179stable, that is, if two members compare as equal, their order in 180the sorted array is undefined. 181The 182.Fn heapsort_b 183function behaves identically to 184.Fn heapsort , 185except that it takes a block, rather than a function pointer. 186The 187.Fn mergesort 188algorithm is stable. 189The 190.Fn mergesort_b 191function behaves identically to 192.Fn mergesort , 193except that it takes a block, rather than a function pointer. 194.Pp 195The 196.Fn qsort 197and 198.Fn qsort_r 199functions are an implementation of C.A.R. 200Hoare's 201.Dq quicksort 202algorithm, 203a variant of partition-exchange sorting; in particular, see 204.An D.E. Knuth Ns 's 205.%T "Algorithm Q" . 206.Sy Quicksort 207takes O N lg N average time. 208This implementation uses median selection to avoid its 209O N**2 worst-case behavior. 210.Pp 211The 212.Fn heapsort 213function is an implementation of 214.An "J.W.J. William" Ns 's 215.Dq heapsort 216algorithm, 217a variant of selection sorting; in particular, see 218.An "D.E. Knuth" Ns 's 219.%T "Algorithm H" . 220.Sy Heapsort 221takes O N lg N worst-case time. 222Its 223.Em only 224advantage over 225.Fn qsort 226is that it uses almost no additional memory; while 227.Fn qsort 228does not allocate memory, it is implemented using recursion. 229.Pp 230The function 231.Fn mergesort 232requires additional memory of size 233.Fa nmemb * 234.Fa size 235bytes; it should be used only when space is not at a premium. 236The 237.Fn mergesort 238function 239is optimized for data with pre-existing order; its worst case 240time is O N lg N; its best case is O N. 241.Pp 242Normally, 243.Fn qsort 244is faster than 245.Fn mergesort 246is faster than 247.Fn heapsort . 248Memory availability and pre-existing order in the data can make this 249untrue. 250.Pp 251The 252.Fn qsort_s 253function behaves the same as 254.Fn qsort_r , except that: 255.Bl -dash 256.It 257The order of arguments is different 258.It 259The order of arguments to 260.Fa compar 261is different 262.It 263if 264.Fa nmemb 265or 266.Fa size 267are greater than 268.Dv RSIZE_MAX , 269or 270.Fa nmemb 271is not zero and 272.Fa compar 273is NULL, then the runtime-constraint handler is called, and 274.Fn qsort_s 275returns an error. 276Note that the handler is called before 277.Fn qsort_s 278returns the error, and the handler function might not return. 279.El 280.Sh RETURN VALUES 281The 282.Fn qsort 283and 284.Fn qsort_r 285functions 286return no value. 287The 288.Fn qsort_s 289function returns zero on success, non-zero on error. 290.Pp 291.Rv -std heapsort mergesort 292.Sh EXAMPLES 293A sample program that sorts an array of 294.Vt int 295values in place using 296.Fn qsort , 297and then prints the sorted array to standard output is: 298.Bd -literal 299#include <stdio.h> 300#include <stdlib.h> 301 302/* 303 * Custom comparison function that compares 'int' values through pointers 304 * passed by qsort(3). 305 */ 306static int 307int_compare(const void *p1, const void *p2) 308{ 309 int left = *(const int *)p1; 310 int right = *(const int *)p2; 311 312 return ((left > right) - (left < right)); 313} 314 315/* 316 * Sort an array of 'int' values and print it to standard output. 317 */ 318int 319main(void) 320{ 321 int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 }; 322 size_t array_size = sizeof(int_array) / sizeof(int_array[0]); 323 size_t k; 324 325 qsort(&int_array, array_size, sizeof(int_array[0]), int_compare); 326 for (k = 0; k < array_size; k++) 327 printf(" %d", int_array[k]); 328 puts(""); 329 return (EXIT_SUCCESS); 330} 331.Ed 332.Sh COMPATIBILITY 333The order of arguments for the comparison function used with 334.Fn qsort_r 335is different from the one used by 336.Fn qsort_s , 337and the GNU libc implementation of 338.Fn qsort_r . 339When porting software written for GNU libc, it is usually possible 340to replace 341.Fn qsort_r 342with 343.Fn qsort_s 344to work around this problem. 345.Pp 346.Fn qsort_s 347is part of the 348.Em optional 349Annex K portion of 350.St -isoC-2011 351and may not be portable to other standards-conforming platforms. 352.Pp 353Previous versions of 354.Fn qsort 355did not permit the comparison routine itself to call 356.Fn qsort 3 . 357This is no longer true. 358.Sh ERRORS 359The 360.Fn heapsort 361and 362.Fn mergesort 363functions succeed unless: 364.Bl -tag -width Er 365.It Bq Er EINVAL 366The 367.Fa size 368argument is zero, or, 369the 370.Fa size 371argument to 372.Fn mergesort 373is less than 374.Dq "sizeof(void *) / 2" . 375.It Bq Er ENOMEM 376The 377.Fn heapsort 378or 379.Fn mergesort 380functions 381were unable to allocate memory. 382.El 383.Sh SEE ALSO 384.Xr sort 1 , 385.Xr radixsort 3 386.Rs 387.%A Hoare, C.A.R. 388.%D 1962 389.%T "Quicksort" 390.%J "The Computer Journal" 391.%V 5:1 392.%P pp. 10-15 393.Re 394.Rs 395.%A Williams, J.W.J 396.%D 1964 397.%T "Heapsort" 398.%J "Communications of the ACM" 399.%V 7:1 400.%P pp. 347-348 401.Re 402.Rs 403.%A Knuth, D.E. 404.%D 1968 405.%B "The Art of Computer Programming" 406.%V Vol. 3 407.%T "Sorting and Searching" 408.%P pp. 114-123, 145-149 409.Re 410.Rs 411.%A McIlroy, P.M. 412.%T "Optimistic Sorting and Information Theoretic Complexity" 413.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" 414.%V January 1992 415.Re 416.Rs 417.%A Bentley, J.L. 418.%A McIlroy, M.D. 419.%T "Engineering a Sort Function" 420.%J "Software--Practice and Experience" 421.%V Vol. 23(11) 422.%P pp. 1249-1265 423.%D November\ 1993 424.Re 425.Sh STANDARDS 426The 427.Fn qsort 428function 429conforms to 430.St -isoC . 431.Fn qsort_s 432conforms to 433.St -isoC-2011 434K.3.6.3.2. 435.Sh HISTORY 436The variants of these functions that take blocks as arguments first appeared in 437Mac OS X. 438This implementation was created by David Chisnall. 439