NAME¶
heapsort
,
mergesort
—
sort functions
LIBRARY¶
library “libbsd”
SYNOPSIS¶
#include
<bsd/stdlib.h>
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 *));
DESCRIPTION¶
The
heapsort
() function is a modified
selection sort. The
mergesort
() function is
a modified merge sort with exponential search intended for sorting data with
pre-existing order.
The
heapsort
() function sorts an array of
nmemb objects, the initial member of which is
pointed to by
base. The size of each object
is specified by
size. The
mergesort
() function 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 algorithm implemented by
heapsort
() is
not stable, that is, if two members compare as
equal, their order in the sorted array is undefined. The
mergesort
() algorithm is stable.
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 worst-case time. Its
only
advantage over
qsort
() is that it uses
almost no additional memory; while
qsort
()
does not allocate memory, it is implemented using recursion.
The function
mergesort
() requires additional
memory of size
nmemb *
size bytes; it should be used only when space
is not at a premium. The
mergesort
()
function is optimized for data with pre-existing order; its worst case time is
O N lg N; its best case is O N.
Normally,
qsort
() is faster than
mergesort
() is faster than
heapsort
(). Memory availability and
pre-existing order in the data can make this untrue.
RETURN VALUES¶
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.
ERRORS¶
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
]
- The
heapsort
() or
mergesort
() functions were unable to
allocate memory.
SEE ALSO¶
sort(1),
radixsort(3)
Williams, J.W.J,
Heapsort, Communications of the
ACM, 7:1, pp. 347-348,
1964.
Knuth, D.E.,
Sorting and Searching, The Art of
Computer Programming, Vol. 3,
pp. 114-123, 145-149,
1968.
McIlroy, P.M.,
Optimistic Sorting and Information Theoretic
Complexity, Fourth Annual ACM-SIAM Symposium on Discrete
Algorithms, January 1992.
Bentley, J.L. and
McIlroy, M.D., Engineering a Sort
Function, Software--Practice and Experience,
Vol. 23(11), pp. 1249-1265,
November 1993.