4.4BSD/usr/share/man/cat3/heapsort.0

QSORT(3)                    BSD Programmer's Manual                   QSORT(3)

NNAAMMEE
     qqssoorrtt,, hheeaappssoorrtt,, mmeerrggeessoorrtt - sort functions

SSYYNNOOPPSSIISS
     ##iinncclluuddee <<ssttddlliibb..hh>>

     _v_o_i_d
     qqssoorrtt(_v_o_i_d _*_b_a_s_e, _s_i_z_e___t _n_m_e_m_b, _s_i_z_e___t _s_i_z_e,
             _i_n_t _(_*_c_o_m_p_a_r_)_(_c_o_n_s_t _v_o_i_d _*_, _c_o_n_s_t _v_o_i_d _*_));

     _i_n_t
     hheeaappssoorrtt(_v_o_i_d _*_b_a_s_e, _s_i_z_e___t _n_m_e_m_b, _s_i_z_e___t _s_i_z_e,
             _i_n_t _(_*_c_o_m_p_a_r_)_(_c_o_n_s_t _v_o_i_d _*_, _c_o_n_s_t _v_o_i_d _*_));

     _i_n_t
     mmeerrggeessoorrtt(_v_o_i_d _*_b_a_s_e, _s_i_z_e___t _n_m_e_m_b, _s_i_z_e___t _s_i_z_e,
             _i_n_t _(_*_c_o_m_p_a_r_)_(_c_o_n_s_t _v_o_i_d _*_, _c_o_n_s_t _v_o_i_d _*_));

DDEESSCCRRIIPPTTIIOONN
     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 _n_m_e_m_b objects, the
     initial member of which is pointed to by _b_a_s_e. The size of each object is
     specified by _s_i_z_e. MMeerrggeessoorrtt() behaves similarly, but _r_e_q_u_i_r_e_s that _s_i_z_e
     be greater than ``sizeof(void *) / 2''.

     The contents of the array _b_a_s_e are sorted in ascending order according to
     a comparison function pointed to by _c_o_m_p_a_r, 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 qqssoorrtt() and hheeaappssoorrtt() are _n_o_t stable, that is, if two mem-
     bers compare as equal, their order in the sorted array is undefined.  The
     function mmeerrggeessoorrtt() is stable.

     The qqssoorrtt() function is 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.  QQssoorrtt() takes O N lg N average time.  This im-
     plementation uses median selection to avoid its O N**2 worst-case behav-
     ior.

     The hheeaappssoorrtt() function is an implementation of J.W.J. William's ``heap-
     sort'' 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
     _o_n_l_y advantage over qqssoorrtt() is that it uses almost no additional memory;
     while qqssoorrtt() does not allocate memory, it is implemented using recur-
     sion.

     The function mmeerrggeessoorrtt() requires additional memory of size _n_m_e_m_b _* _s_i_z_e
     bytes; it should be used only when space is not at a premium.
     MMeerrggeessoorrtt() 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 un-
     true.

RREETTUURRNN VVAALLUUEESS
     The qqssoorrtt() function returns no value.

     Upon successful completion, hheeaappssoorrtt() and mmeerrggeessoorrtt() return 0.  Other-
     wise, they return -1 and the global variable _e_r_r_n_o is set to indicate the
     error.

EERRRROORRSS
     The hheeaappssoorrtt() function succeeds unless:

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

     [ENOMEM]      HHeeaappssoorrtt() or mmeerrggeessoorrtt() 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.

SSEEEE AALLSSOO
     sort(1),  radixsort(3)

     Hoare, C.A.R., "Quicksort", _T_h_e _C_o_m_p_u_t_e_r _J_o_u_r_n_a_l, 5:1, pp. 10-15, 1962.

     Williams, J.W.J, "Heapsort", _C_o_m_m_u_n_i_c_a_t_i_o_n_s _o_f _t_h_e _A_C_M, 7:1, pp. 347-348,
     1964.

     Knuth, D.E., "Sorting and Searching", _T_h_e _A_r_t _o_f _C_o_m_p_u_t_e_r _P_r_o_g_r_a_m_m_i_n_g,
     Vol. 3, pp. 114-123, 145-149, 1968.

     Mcilroy, P.M., "Optimistic Sorting and Information Theoretic Complexity",
     _F_o_u_r_t_h _A_n_n_u_a_l _A_C_M_-_S_I_A_M _S_y_m_p_o_s_i_u_m _o_n _D_i_s_c_r_e_t_e _A_l_g_o_r_i_t_h_m_s, January 1992.

     Bentley, J.L., "Engineering a Sort Function", _b_e_n_t_l_e_y_@_r_e_s_e_a_r_c_h_._a_t_t_._c_o_m,
     January 1992.

SSTTAANNDDAARRDDSS
     The qqssoorrtt() function conforms to ANSI C X3.159-1989 (``ANSI C '').

4.4BSD                           June 4, 1993                                2