QSORT(3) BSD Library Functions Manual QSORT(3)

NAME
     qqssoorrtt, qqssoorrttrr, hheeaappssoorrtt, mmeerrggeessoorrtt - sort functions

LLIIBBRRAARRYY
     Standard C Library (libc, -lc)

SYNOPSIS
     ##iinncclluuddee <>

     void
     qqssoorrtt(void *base, sizet nmemb, sizet size,
         int (*compar)(const void *, const void *));

     void
     qqssoorrttrr(void *base, sizet nmemb, sizet size, void *thunk,
         int (*compar)(void *, const void *, const void *));

     int
     hheeaappssoorrtt(void *base, sizet nmemb, sizet size,
         int (*compar)(const void *, const void *));

     int
     mmeerrggeessoorrtt(void *base, sizet nmemb, sizet size,
         int (*compar)(const void *, const void *));

DESCRIPTION
     The qqssoorrtt() function is a modified partition-exchange sort, or quicksort.
     The hheeaappssoorrtt() function is a modified selection sort.  The mmeerrggeessoorrtt()
     function is a modified merge sort with exponential search intended for
     sorting data with pre-existing order.

     The qqssoorrtt() and hheeaappssoorrtt() 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.  The mmeerrggeessoorrtt() 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 qqssoorrttrr() function behaves identically to qqssoorrtt(), except that it
     takes an additional argument, thunk, which is passed unchanged as the
     first argument to function pointed to compar.  This allows the comparison
     function to access additional data without using global variables, and
     thus qqssoorrttrr() is suitable for use in functions which must be reentrant.

     The algorithms implemented by qqssoorrtt(), qqssoorrttrr(), and hheeaappssoorrtt() are not
     stable, that is, if two members compare as equal, their order in the
     sorted array is undefined.  The mmeerrggeessoorrtt() algorithm is stable.

     The qqssoorrtt() and qqssoorrttrr() functions are an implementation of C.A.R.
     Hoare's ``quicksort'' algorithm, a variant of partition-exchange sorting;
     in particular, see D.E. Knuth's Algorithm Q.  QQuuiicckkssoorrtt takes O N lg N
     average time.  This implementation uses median selection to avoid its O
     N**2 worst-case behavior.

     The hheeaappssoorrtt() 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.  HHeeaappssoorrtt takes O N lg N worst-case time.
     Its only advantage over qqssoorrtt() is that it uses almost no additional mem-
     ory; while qqssoorrtt() does not allocate memory, it is implemented using
     recursion.

     The function mmeerrggeessoorrtt() requires additional memory of size nmemb * size
     bytes; it should be used only when space is not at a premium.  The
     mmeerrggeessoorrtt() 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, qqssoorrtt() is faster than mmeerrggeessoorrtt() is faster than hheeaappssoorrtt().
     Memory availability and pre-existing order in the data can make this
     untrue.

RETURN VALUES
     The qqssoorrtt() and qqssoorrttrr() functions return no value.

     The hheeaappssoorrtt() and mmeerrggeessoorrtt() functions return the value 0 if success-
     ful; otherwise the value -1 is returned and the global variable errno is
     set to indicate the error.

EERRRROORRSS
     The hheeaappssoorrtt() and mmeerrggeessoorrtt() functions succeed unless:

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

     [ENOMEM]           The hheeaappssoorrtt() or mmeerrggeessoorrtt() functions were unable to
                        allocate memory.

CCOOMMPPAATTIIBBIILLIITTYY
     Previous versions of qqssoorrtt() did not permit the comparison routine itself
     to call qqssoorrtt(3).  This is no longer true.

SEE ALSO
     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,
     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.

STANDARDS     The qqssoorrtt() function conforms to ISO/IEC 9899:1990 (``ISO C90'').

BSD                           September 30, 2003                           BSD