Manpages - heapsort.3bsd

(See

for include usage.)

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

function sorts an array of

objects, the initial member of which is pointed to by

The size of each object is specified by

The

function 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 algorithm implemented by

stable, that is, if two members compare as equal, their order in the sorted array is undefined. The

algorithm is stable.

The

function is an implementation of

algorithm, a variant of selection sorting; in particular, see

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. The

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,

is faster than

Memory availability and pre-existing order in the data can make this untrue.

The

and

functions succeed unless:

The

argument is zero, or, the

argument to

is less than

The

functions were unable to allocate memory.