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