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.27 2020/02/08 01:09:57 jsg Exp $ 33.\" 34.Dd $Mdocdate: February 8 2020 $ 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 int 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 EXAMPLES 150.Bd -literal 151#include <stdio.h> 152#include <stdlib.h> 153#include <string.h> 154 155char *array[] = { "XX", "YYY", "Z" }; 156#define N (sizeof(array) / sizeof(array[0])) 157 158int 159cmp(const void *a, const void *b) 160{ 161 /* 162 * a and b point to elements of the array. 163 * Cast and dereference to obtain the actual elements, 164 * which are also pointers in this case. 165 */ 166 size_t lena = strlen(*(const char **)a); 167 size_t lenb = strlen(*(const char **)b); 168 /* 169 * Do not subtract the lengths. The difference between values 170 * cannot be represented by an int. 171 */ 172 return lena < lenb ? -1 : lena > lenb; 173} 174 175int 176main() 177{ 178 size_t i; 179 180 qsort(array, N, sizeof(array[0]), cmp); 181 for (i = 0; i < N; i++) 182 printf("%s\en", array[i]); 183} 184.Ed 185.Pp 186It is almost always an error to use subtraction to compute the return value 187of the comparison function. 188.Sh ERRORS 189The 190.Fn heapsort 191and 192.Fn mergesort 193functions succeed unless: 194.Bl -tag -width Er 195.It Bq Er EINVAL 196The 197.Fa size 198argument is zero, or the 199.Fa size 200argument to 201.Fn mergesort 202is less than 203.Dq "sizeof(void *) / 2" . 204.It Bq Er ENOMEM 205.Fn heapsort 206or 207.Fn mergesort 208were unable to allocate memory. 209.El 210.Sh SEE ALSO 211.Xr sort 1 , 212.Xr radixsort 3 213.Rs 214.%A Hoare, C.A.R. 215.%D 1962 216.%T "Quicksort" 217.%J "The Computer Journal" 218.%V 5:1 219.%P pp. 10-15 220.Re 221.Rs 222.%A Williams, J.W.J 223.%D 1964 224.%T "Heapsort" 225.%J "Communications of the ACM" 226.%V 7:1 227.%P pp. 347\-348 228.Re 229.Rs 230.%A Knuth, D.E. 231.%D 1968 232.%B "The Art of Computer Programming" 233.%V Vol. 3 234.%T "Sorting and Searching" 235.%P pp. 114\-123, 145\-149 236.Re 237.Rs 238.%A McIlroy, P.M. 239.%T "Optimistic Sorting and Information Theoretic Complexity" 240.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" 241.%P pp. 467\-464 242.%D January 1993 243.Re 244.Rs 245.%A Bentley, J.L. 246.%A McIlroy, M.D. 247.%T "Engineering a Sort Function" 248.%J "Software \- Practice and Experience" 249.%V Vol. 23(11) 250.%P pp. 1249\-1265 251.%D November 1993 252.Re 253.Rs 254.%A Musser, D. 255.%T "Introspective Sorting and Selection Algorithms" 256.%J "Software \- Practice and Experience" 257.%V Vol. 27(8) 258.%P pp. 983\-993 259.%D August 1997 260.Re 261.Sh STANDARDS 262Previous versions of 263.Fn qsort 264did not permit the comparison routine itself to call 265.Fn qsort . 266This is no longer true. 267.Pp 268The 269.Fn qsort 270function conforms to 271.St -ansiC . 272.Sh HISTORY 273A 274.Fn qsort 275function first appeared in 276.At v2 . 277