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