The Fn qsort and Fn heapsort functions sort an array of Fa nmemb objects, the initial member of which is pointed to by Fa base . The size of each object is specified by Fa size .
The contents of the array are sorted in ascending order according to a comparison function pointed to by Fa compar , which is called with two arguments that point 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 Fn qsort and Fn heapsort are not stable, that is, if two members compare as equal, their order in the sorted array is undefined.
The Fn qsort 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. Fn Qsort takes O N lg N average time. This implementation uses median selection to avoid the traditional O N**2 worst-case behavior.
The Fn heapsort 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. Fn Heapsort takes O N lg N worst-case time. Its only advantage over Fn qsort is that it uses no additional memory.
Upon successful completion, Fn heapsort returns 0. Otherwise, it returns -1 and the global variable errno is set to indicate the error.