qsort,
heapsort,
mergesort —
sort functions
#include
<stdlib.h>
void
qsort(
void
*base,
size_t
nmemb,
size_t
size,
int
(*compar)(const void *, const void *));
int
heapsort(
void
*base,
size_t
nmemb,
size_t
size,
int
(*compar)(const void *, const void *));
int
mergesort(
void
*base,
size_t
nmemb,
size_t
size,
int
(*compar)(const void *, const void *));
The
qsort() function is a modified
partitionexchange sort, or quicksort. The
heapsort() function is a modified selection sort.
The
mergesort() function is a modified merge sort
with exponential search intended for sorting data with preexisting order.
The
qsort() and
heapsort() functions sort an array of
nmemb objects, the initial member of which is
pointed to by
base. The size of each object
is specified by
size.
mergesort() behaves similarly, but
requires that
size be greater than “sizeof(void *) /
2”.
The contents of the array
base are sorted in
ascending order according to a comparison function pointed to by
compar, which requires two arguments pointing
to the objects being compared.
The comparison function must return an integer less than, equal to, or greater
than zero if the first argument is considered to be respectively less than,
equal to, or greater than the second.
The functions
qsort() and
heapsort() are
not
stable, that is, if two members compare as equal, their order in the sorted
array is undefined. The function
mergesort() is
stable.
The
qsort() function is an implementation of C.A.R.
Hoare's “quicksort” algorithm, a variant of partitionexchange
sorting; in particular, see D.E. Knuth's Algorithm Q.
qsort() takes O N lg N average time. This
implementation uses median selection to avoid its O N**2 worstcase behavior
and will fall back to
heapsort() if the recursion
depth exceeds 2 lg N.
The
heapsort() function is an implementation of
J.W.J. William's “heapsort” algorithm, a variant of selection
sorting; in particular, see D.E. Knuth's Algorithm H.
heapsort() takes O N lg N worstcase time. This
implementation of
heapsort() is implemented
without recursive function calls.
The function
mergesort() requires additional memory
of size
nmemb *
size bytes; it should be used only when space
is not at a premium.
mergesort() is optimized for
data with preexisting order; its worst case time is O N lg N; its best case
is O N.
Normally,
qsort() is faster than
mergesort(), which is faster than
heapsort(). Memory availability and preexisting
order in the data can make this untrue.
The
heapsort() and
mergesort() functions return the value 0
if successful; otherwise the value 1 is returned and the global
variable
errno is set to indicate the error.
The
heapsort() and
mergesort() functions succeed unless:


 [
EINVAL
]
 The size argument is zero,
or the size argument to
mergesort() is less than “sizeof(void
*) / 2”.


 [
ENOMEM
]
 heapsort() or
mergesort() were unable to allocate
memory.
sort(1),
radixsort(3)
Hoare, C.A.R.,
Quicksort, The Computer Journal,
5:1, pp. 1015,
1962.
Williams, J.W.J,
Heapsort, Communications of the
ACM, 7:1, pp. 347348,
1964.
Knuth, D.E.,
Sorting and Searching, The Art of
Computer Programming, Vol. 3,
pp. 114123, 145149,
1968.
McIlroy, P.M.,
Optimistic Sorting and Information Theoretic
Complexity, Fourth Annual ACMSIAM Symposium on Discrete
Algorithms, pp. 467464,
January 1993.
Bentley, J.L. and
McIlroy, M.D., Engineering a Sort
Function, Software  Practice and Experience,
Vol. 23(11), pp. 12491265,
November 1993.
Musser, D.,
Introspective Sorting and Selection Algorithms,
Software  Practice and Experience, Vol.
27(8), pp. 983993, August
1997.
Previous versions of
qsort() did not permit the
comparison routine itself to call
qsort(). This
is no longer true.
The
qsort() function conforms to
ANSI X3.1591989
(“ANSI C89”).
A
qsort() function first appeared in
Version 3 AT&T UNIX.