9.3 Array Sort Function

To sort an array using an arbitrary comparison function, use the qsort function. The prototype for this function is in stdlib.h.

Function: void qsort (void *array, size_t count, size_t size, comparison_fn_t compare)

Preliminary: | MT-Safe | AS-Safe | AC-Unsafe corrupt | See POSIX Safety Concepts.

The qsort function sorts the array array. The array contains count elements, each of which is of size size.

The compare function is used to perform the comparison on the array elements. This function is called with two pointer arguments and should return an integer less than, equal to, or greater than zero corresponding to whether its first argument is considered less than, equal to, or greater than its second argument. The function must not alter the array’s contents, and must define a total ordering on the array elements, including any unusual values such as floating-point NaN (see Infinity and NaN). Because the sorting process can move elements, the function’s return value must not depend on the element addresses or the relative positions of elements within the array, as these are meaningless while qsort is running.

Warning: If two elements compare equal, their order after sorting is unpredictable. That is to say, the sorting is not stable. This can make a difference when the comparison considers only part of the elements and two elements that compare equal may differ in other respects. To ensure a stable sort in this situation, you can augment each element with an appropriate tie-breaking value, such as its original array index.

Here is a simple example of sorting an array of long int in numerical order, using the comparison function defined above (see Defining the Comparison Function):

{
  long int *array;
  size_t nmemb;
  ...
  qsort (array, nmemb, sizeof *array, compare_long_ints);
}

The qsort function derives its name from the fact that it was originally implemented using the “quick sort” algorithm.

The implementation of qsort attempts to allocate auxiliary memory and use the merge sort algorithm, without violating C standard requirement that arguments passed to the comparison function point within the array. If the memory allocation fails, qsort resorts to a slower algorithm.