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 April 19, 2023 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 , except that: 252.Bl -dash 253.It 254The order of arguments is different 255.It 256The order of arguments to 257.Fa compar 258is different 259.It 260If 261.Fa nmemb 262or 263.Fa size 264are greater than 265.Dv RSIZE_MAX , 266or 267.Fa nmemb 268is not zero and 269.Fa compar 270is 271.Dv NULL 272or 273.Fa size 274is zero, then the runtime-constraint handler is called, and 275.Fn qsort_s 276returns an error. 277Note that the handler is called before 278.Fn qsort_s 279returns the error, and the handler function might not return. 280.El 281.Sh RETURN VALUES 282The 283.Fn qsort 284and 285.Fn qsort_r 286functions 287return no value. 288The 289.Fn qsort_s 290function returns zero on success, non-zero on error. 291.Pp 292.Rv -std heapsort mergesort 293.Sh EXAMPLES 294A sample program that sorts an array of 295.Vt int 296values in place using 297.Fn qsort , 298and then prints the sorted array to standard output is: 299.Bd -literal 300#include <stdio.h> 301#include <stdlib.h> 302 303/* 304 * Custom comparison function that compares 'int' values through pointers 305 * passed by qsort(3). 306 */ 307static int 308int_compare(const void *p1, const void *p2) 309{ 310 int left = *(const int *)p1; 311 int right = *(const int *)p2; 312 313 return ((left > right) - (left < right)); 314} 315 316/* 317 * Sort an array of 'int' values and print it to standard output. 318 */ 319int 320main(void) 321{ 322 int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 }; 323 size_t array_size = sizeof(int_array) / sizeof(int_array[0]); 324 size_t k; 325 326 qsort(&int_array, array_size, sizeof(int_array[0]), int_compare); 327 for (k = 0; k < array_size; k++) 328 printf(" %d", int_array[k]); 329 puts(""); 330 return (EXIT_SUCCESS); 331} 332.Ed 333.Sh COMPATIBILITY 334The order of arguments for the comparison function used with 335.Fn qsort_r 336is different from the one used by 337.Fn qsort_s , 338and the GNU libc implementation of 339.Fn qsort_r . 340When porting software written for GNU libc, it is usually possible 341to replace 342.Fn qsort_r 343with 344.Fn qsort_s 345to work around this problem. 346.Pp 347.Fn qsort_s 348is part of the 349.Em optional 350Annex K portion of 351.St -isoC-2011 352and may not be portable to other standards-conforming platforms. 353.Pp 354Previous versions of 355.Fn qsort 356did not permit the comparison routine itself to call 357.Fn qsort 3 . 358This is no longer true. 359.Sh ERRORS 360The 361.Fn heapsort 362and 363.Fn mergesort 364functions succeed unless: 365.Bl -tag -width Er 366.It Bq Er EINVAL 367The 368.Fa size 369argument is zero, or, 370the 371.Fa size 372argument to 373.Fn mergesort 374is less than 375.Dq "sizeof(void *) / 2" . 376.It Bq Er ENOMEM 377The 378.Fn heapsort 379or 380.Fn mergesort 381functions 382were unable to allocate memory. 383.El 384.Sh SEE ALSO 385.Xr sort 1 , 386.Xr radixsort 3 387.Rs 388.%A Hoare, C.A.R. 389.%D 1962 390.%T "Quicksort" 391.%J "The Computer Journal" 392.%V 5:1 393.%P pp. 10-15 394.Re 395.Rs 396.%A Williams, J.W.J 397.%D 1964 398.%T "Heapsort" 399.%J "Communications of the ACM" 400.%V 7:1 401.%P pp. 347-348 402.Re 403.Rs 404.%A Knuth, D.E. 405.%D 1968 406.%B "The Art of Computer Programming" 407.%V Vol. 3 408.%T "Sorting and Searching" 409.%P pp. 114-123, 145-149 410.Re 411.Rs 412.%A McIlroy, P.M. 413.%T "Optimistic Sorting and Information Theoretic Complexity" 414.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" 415.%V January 1992 416.Re 417.Rs 418.%A Bentley, J.L. 419.%A McIlroy, M.D. 420.%T "Engineering a Sort Function" 421.%J "Software--Practice and Experience" 422.%V Vol. 23(11) 423.%P pp. 1249-1265 424.%D November\ 1993 425.Re 426.Sh STANDARDS 427The 428.Fn qsort 429function 430conforms to 431.St -isoC . 432.Fn qsort_s 433conforms 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 POSIX. 446