Does the qsort() function provide performance guarantees?

Question

Does the C standard require the standard-library qsort() function provide a specific level of performance? The name suggests the use of an O(n log n) algorithm such as quicksort. Could a standards-conforming library implement it using the O(n^2) insertion sort, or even the O(n!) bogosort?

Answer 1

According to the C89, C99, C11, and C17 standards, no particular big-O behavior is required.

This is the language from the C89 standard, under heading 7.10.5.2. The other standards contain identical language.

Synopsis

#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

Description

The qsort function sorts an array of nmemb objects, the initial element of which is pointed to by base. The size of each object is specified by size.

The contents of the array are sorted into ascending order according to a comparison function pointed to by compar, which is called with two arguments that point to the objects being compared. The function shall 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.

If two elements compare as equal, their order in the sorted array is unspecified.

Returns

The qsort function returns no value.

The standard does not specify a particular algorithm or particular speed. In fact, it goes out of its way to allow more sorting algorithms by not requiring a stable sort. I interpret this to mean that Bogosort is a standards-compliant way to implement qsort.