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.