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