What is the complexity of qsort function from the standard library in C? If possible, please provide a reference also.
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
According to cppreference.com, which is a reasonably reliable source for documentation about the C language:
Despite the name, neither C nor POSIX standards require this function to be implemented using quicksort or make any complexity or stability guarantees.
I have a draft of the C ISO standard, which says the following about qsort:
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 resulting sorted array is unspecified.
Returns:
The qsort function returns no value.
This supports what the reference site says, since there is no mention of any complexity guarantees here.
So overall you cannot assume that the runtime will be O(n log n) on average or in worst-case. There's a history of implementations that use heuristics that can degenerate in the worst case; search "A Killer Adversary for Quicksort" for details.
Contrast this with the C++ std::sort, which is guaranteed to run in time O(n log n) in the worst-case.