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.\" $OpenBSD: qsort.3,v 1.20 2017/05/20 13:09:01 millert Exp $ 33.\" 34.Dd $Mdocdate: May 20 2017 $ 35.Dt QSORT 3 36.Os 37.Sh NAME 38.Nm qsort , 39.Nm heapsort , 40.Nm mergesort 41.Nd sort functions 42.Sh SYNOPSIS 43.In stdlib.h 44.Ft void 45.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 46.Ft int 47.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 48.Ft int 49.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 50.Sh DESCRIPTION 51The 52.Fn qsort 53function is a modified partition-exchange sort, or quicksort. 54The 55.Fn heapsort 56function is a modified selection sort. 57The 58.Fn mergesort 59function is a modified merge sort with exponential search 60intended for sorting data with pre-existing order. 61.Pp 62The 63.Fn qsort 64and 65.Fn heapsort 66functions sort an array of 67.Fa nmemb 68objects, the initial member of which is pointed to by 69.Fa base . 70The size of each object is specified by 71.Fa size . 72.Fn mergesort 73behaves similarly, but 74.Em requires 75that 76.Fa size 77be greater than 78.Dq "sizeof(void *) / 2" . 79.Pp 80The contents of the array 81.Fa base 82are sorted in ascending order according to 83a comparison function pointed to by 84.Fa compar , 85which requires two arguments pointing to the objects being 86compared. 87.Pp 88The comparison function must return an integer less than, equal to, or 89greater than zero if the first argument is considered to be respectively 90less than, equal to, or greater than the second. 91.Pp 92The functions 93.Fn qsort 94and 95.Fn heapsort 96are 97.Em not 98stable, that is, if two members compare as equal, their order in 99the sorted array is undefined. 100The function 101.Fn mergesort 102is stable. 103.Pp 104The 105.Fn qsort 106function is an implementation of C.A.R. Hoare's 107.Dq quicksort 108algorithm, 109a variant of partition-exchange sorting; in particular, see D.E. Knuth's 110Algorithm Q. 111.Fn qsort 112takes O N lg N average time. 113This implementation uses median selection to avoid its 114O N**2 worst-case behavior and will fall back to 115.Fn heapsort 116if the recursion depth exceeds 2 lg N. 117.Pp 118The 119.Fn heapsort 120function is an implementation of J.W.J. William's 121.Dq heapsort 122algorithm, 123a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. 124.Fn heapsort 125takes O N lg N worst-case time. 126This implementation of 127.Fn heapsort 128is implemented without recursive function calls. 129.Pp 130The function 131.Fn mergesort 132requires additional memory of size 133.Fa nmemb * 134.Fa size 135bytes; it should be used only when space is not at a premium. 136.Fn mergesort 137is optimized for data with pre-existing order; its worst case 138time is O N lg N; its best case is O N. 139.Pp 140Normally, 141.Fn qsort 142is faster than 143.Fn mergesort , 144which is faster than 145.Fn heapsort . 146Memory availability and pre-existing order in the data can make this untrue. 147.Sh RETURN VALUES 148.Rv -std heapsort mergesort 149.Sh ERRORS 150The 151.Fn heapsort 152and 153.Fn mergesort 154functions succeed unless: 155.Bl -tag -width Er 156.It Bq Er EINVAL 157The 158.Fa size 159argument is zero, or the 160.Fa size 161argument to 162.Fn mergesort 163is less than 164.Dq "sizeof(void *) / 2" . 165.It Bq Er ENOMEM 166.Fn heapsort 167or 168.Fn mergesort 169were unable to allocate memory. 170.El 171.Sh SEE ALSO 172.Xr sort 1 , 173.Xr radixsort 3 174.Rs 175.%A Hoare, C.A.R. 176.%D 1962 177.%T "Quicksort" 178.%J "The Computer Journal" 179.%V 5:1 180.%P pp. 10-15 181.Re 182.Rs 183.%A Williams, J.W.J 184.%D 1964 185.%T "Heapsort" 186.%J "Communications of the ACM" 187.%V 7:1 188.%P pp. 347\-348 189.Re 190.Rs 191.%A Knuth, D.E. 192.%D 1968 193.%B "The Art of Computer Programming" 194.%V Vol. 3 195.%T "Sorting and Searching" 196.%P pp. 114\-123, 145\-149 197.Re 198.Rs 199.%A McIlroy, P.M. 200.%T "Optimistic Sorting and Information Theoretic Complexity" 201.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" 202.%P pp. 467\-464 203.%D January 1993 204.Re 205.Rs 206.%A Bentley, J.L. 207.%A McIlroy, M.D. 208.%T "Engineering a Sort Function" 209.%J "Software \- Practice and Experience" 210.%V Vol. 23(11) 211.%P pp. 1249\-1265 212.%D November 1993 213.Re 214.Rs 215.%A Musser, D. 216.%T "Introspective Sorting and Selection Algorithms" 217.%J "Software \- Practice and Experience" 218.%V Vol. 27(8) 219.%P pp. 983\-993 220.%D August 1997 221.Re 222.Sh STANDARDS 223Previous versions of 224.Fn qsort 225did not permit the comparison routine itself to call 226.Fn qsort . 227This is no longer true. 228.Pp 229The 230.Fn qsort 231function conforms to 232.St -ansiC . 233.Sh HISTORY 234A 235.Fn qsort 236function first appeared in 237.At v3 . 238