Table of Contents
The
function is a modified partition-exchange sort, or quicksort. The 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
and functions sort an array of objects, the initial member of which
is pointed to by The size of each object is specified by behaves similarly,
but that be greater than The contents of the array are sorted in ascending
order according to a comparison function pointed to by 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 and are stable, that is, if two
members compare as equal, their order in the sorted array is undefined.
The function is stable. The 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. takes O N lg N average time. This implementation
uses median selection to avoid its O N**2 worst-case behavior. The 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. takes O N lg N worst-case
time. Its advantage over is that it uses almost no additional memory;
while does not allocate memory, it is implemented using recursion. The
function requires additional memory of size bytes; it should be used
only when space is not at a premium. is optimized for data with pre-existing
order; its worst case time is O N lg N; its best case is O N. Normally,
is faster than is faster than Memory availability and pre-existing order
in the data can make this untrue.
The function returns no
value. Upon successful completion, and return 0. Otherwise, they return
-1 and the global variable is set to indicate the error.
The function
succeeds unless: The argument is zero, or, the argument to is less
than or were unable to allocate memory.
Previous versions
of did not permit the comparison routine itself to call This is no longer
true.
The function
conforms to
Table of Contents