Which sorting algorithm does qsort() use?

Question

Does the function qsort() in stdlib.h actually use quicksort algorithm, as the name suggests?

Answer 1

The qsort() function may be implemented using any sort algorithm that the library implementer chooses, but the name suggests that the algorithm should be close to optimal. Using an O(N²) algorithm would be permissible, but a major QoI (quality of implementation) issue.

It is worth noting that comparison is quite expensive with the qsort() interface; any sort algorithm that increases the number of comparisons to reduce the number of moves (which can also be expensive if you are not shuffling pointers) may lead to worse performance. However, that's an issue for the library implementer to be concerned with. Unless you find that the library implementation is horrid (which is pretty unlikely these days), use it and don't worry.

The C++ sort algorithm can run rings around C's qsort.

Answer 2

The C11 standard does not specify. So any reasonable O(n log n) would be acceptable.