NAME

       heapsort, mergesort — sort functions

LIBRARY

       Utility functions from BSD systems (libbsd, -lbsd)

SYNOPSIS

       #include <stdlib.h>
       (See libbsd(7) for include usage.)

       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(3bsd)

       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.

Debian                                         September 30, 2003                                 heapsort(3bsd)