*nix Documentation Project
·  Home
 +   man pages
·  Linux HOWTOs
·  FreeBSD Tips
·  *niX Forums

  man pages->OpenBSD man pages -> mergesort (3)              



NAME    [Toc]    [Back]

     qsort, heapsort, mergesort - sort functions

SYNOPSIS    [Toc]    [Back]

     #include <stdlib.h>

     qsort(void *base, size_t nmemb, size_t size,
             int (*compar)(const void *, const void *));

     heapsort(void *base, size_t nmemb, size_t size,
             int (*compar)(const void *, const void *));

     mergesort(void *base, size_t nmemb, size_t size,
             int (*compar)(const void *, const void *));

DESCRIPTION    [Toc]    [Back]

     The qsort() function is a modified partition-exchange  sort,
or quicksort.
     The  heapsort()  function is a modified selection sort.  The
     function is a modified merge sort  with  exponential  search
intended for
     sorting data with pre-existing 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
     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
     algorithm,  a variant of partition-exchange 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
worst-case behavior.

     The heapsort()  function  is  an  implementation  of  J.W.J.
     ``heapsort''  algorithm,  a variant of selection sorting; in
     see D.E. Knuth's Algorithm H.  heapsort() takes  O  N  lg  N
worst-case time.
     This implementation of heapsort() is implemented without recursive function

     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  pre-existing  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 pre-existing  order  in
the data can
     make this untrue.

RETURN VALUES    [Toc]    [Back]

     The qsort() function returns no value.

     Upon  successful  completion, heapsort() and mergesort() return 0.  Otherwise,
 they return -1 and the global variable errno is set to
indicate the

ERRORS    [Toc]    [Back]

     The heapsort() and mergesort() functions succeed unless:

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

     [ENOMEM]      heapsort() or mergesort() were unable to allocate memory.

SEE ALSO    [Toc]    [Back]

     sort(1), radixsort(3)

     Hoare, C.A.R., "Quicksort", The Computer Journal,  5:1,  pp.
10-15, 1962.

     Williams, J.W.J, "Heapsort", Communications of the ACM, 7:1,
pp. 347-348,

     Knuth, D.E., "Sorting and Searching", The  Art  of  Computer
     Vol. 3, pp. 114-123, 145-149, 1968.

     McIlroy, P.M., "Optimistic Sorting and Information Theoretic
     Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.
     January 1993.

     Bentley,  J.L.  and McIlroy, M.D., "Engineering a Sort Function", Software
     - Practice  and  Experience,  Vol.  23(11),  pp.  1249-1265,
November 1993.

STANDARDS    [Toc]    [Back]

     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.159-1989  (``ANSI

OpenBSD      3.6                           June      4,      1993
[ Back ]
 Similar pages
Name OS Title
radixsort NetBSD radix sort
sradixsort OpenBSD radix sort
qsort IRIX quick sort
sradixsort NetBSD radix sort
radixsort FreeBSD radix sort
qsort IRIX quicker sort
tsort IRIX topological sort
tsort HP-UX topological sort
radixsort OpenBSD radix sort
lsort IRIX Sort the elements of a list
Copyright © 2004-2005 DeniX Solutions SRL
newsletter delivery service