1.\" Copyright (c) 1990, 1991 The Regents of the University of California. 2.\" 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.\" %sccs.include.redist.man% 9.\" 10.\" @(#)qsort.3 6.11 (Berkeley) 04/16/93 11.\" 12.Dd 13.Dt QSORT 3 14.Os 15.Sh NAME 16.Nm qsort, heapsort, mergesort 17.Nd sort functions 18.Sh SYNOPSIS 19.Fd #include <stdlib.h> 20.Ft void 21.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 22.Ft int 23.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 24.Ft int 25.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 26.Sh DESCRIPTION 27The 28.Fn qsort 29function is a modified partition-exchange sort, or quicksort. 30The 31.Fn heapsort 32function is a modified selection sort. 33The 34.Fn mergesort 35function is a modified merge sort with exponential search 36intended for sorting data with pre-existing order. 37.Pp 38The 39.Fn qsort 40and 41.Fn heapsort 42functions sort an array of 43.Fa nmemb 44objects, the initial member of which is pointed to by 45.Fa base . 46The size of each object is specified by 47.Fa size . 48.Fn Mergesort 49behaves similarly, but 50.Em requires 51that 52.Fa size 53be greater than 54.Dq "sizeof(void *) / 2" . 55.Pp 56The contents of the array 57.Fa base 58are sorted in ascending order according to 59a comparison function pointed to by 60.Fa compar , 61which requires two arguments pointing to the objects being 62compared. 63.Pp 64The comparison function must return an integer less than, equal to, or 65greater than zero if the first argument is considered to be respectively 66less than, equal to, or greater than the second. 67.Pp 68The functions 69.Fn qsort 70and 71.Fn heapsort 72are 73.Em not 74stable, that is, if two members compare as equal, their order in 75the sorted array is undefined. 76The function 77.Fn mergesort 78is stable. 79.Pp 80The 81.Fn qsort 82function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, 83a variant of partition-exchange sorting; in particular, see D.E. Knuth's 84Algorithm Q. 85.Fn Qsort 86takes O N lg N average time. 87This implementation uses median selection to avoid its 88O N**2 worst-case behavior. 89.Pp 90The 91.Fn heapsort 92function is an implementation of J.W.J. William's ``heapsort'' algorithm, 93a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. 94.Fn Heapsort 95takes O N lg N worst-case time. 96Its 97.Em only 98advantage over 99.Fn qsort 100is that it uses almost no additional memory; while 101.Fn qsort 102does not allocate memory, it is implemented using recursion. 103.Pp 104The function 105.Fn mergesort 106requires additional memory of size 107.Fa nmemb * 108.Fa size 109bytes; it should be used only when space is not at a premium. 110.Fn Mergesort 111is optimized for data with pre-existing order; its worst case 112time is O N lg N; its best case is O N. 113.Pp 114Normally, 115.Fn qsort 116is faster than 117.Fn mergesort 118is faster than 119.Fn heapsort . 120Memory availability and pre-existing order in the data can make this 121untrue. 122.Sh RETURN VALUES 123The 124.Fn qsort 125function 126returns no value. 127.Pp 128Upon successful completion, 129.Fn heapsort 130and 131.Fn mergesort 132return 0. 133Otherwise, they return \-1 and the global variable 134.Va errno 135is set to indicate the error. 136.Sh ERRORS 137The 138.Fn heapsort 139function succeeds unless: 140.Bl -tag -width Er 141.It Bq Er EINVAL 142The 143.Fa size 144argument is zero, or, 145the 146.Fa size 147argument to 148.Fn mergesort 149is less than 150.Dq "sizeof(void *) / 2" . 151.It Bq Er ENOMEM 152.Fn Heapsort 153or 154.Fn mergesort 155were unable to allocate memory. 156.El 157.Sh COMPATIBILITY 158Previous versions of 159.Fn qsort 160did not permit the comparison routine itself to call 161.Fn qsort 3 . 162This is no longer true. 163.Sh SEE ALSO 164.Xr sort 1 , 165.Xr radixsort 3 166.Rs 167.%A Hoare, C.A.R. 168.%D 1962 169.%T "Quicksort" 170.%J "The Computer Journal" 171.%V 5:1 172.%P pp. 10-15 173.Re 174.Rs 175.%A Williams, J.W.J 176.%D 1964 177.%T "Heapsort" 178.%J "Communications of the ACM" 179.%V 7:1 180.%P pp. 347-348 181.Re 182.Rs 183.%A Knuth, D.E. 184.%D 1968 185.%B "The Art of Computer Programming" 186.%V Vol. 3 187.%T "Sorting and Searching" 188.%P pp. 114-123, 145-149 189.Re 190.Rs 191.%A Mcilroy, P.M. 192.%T "Optimistic Sorting and Information Theoretic Complexity" 193.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" 194.%V January 1992 195.Re 196.Rs 197.%A Bentley, J.L. 198.%T "Engineering a Sort Function" 199.%J "bentley@research.att.com" 200.%V January 1992 201.Re 202.Sh STANDARDS 203The 204.Fn qsort 205function 206conforms to 207.St -ansiC . 208