is a C standard library function that implements a sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the "quicker sort" algorithm (a quicksort variant due to R. S. Scowen), which was originally used to implement it in the Unix C library, although the C standard does not require it to implement quicksort. It comes from <code><stdlib.h></code> (or <code><cstdlib></code> in C++ Standard Library).
The ability to operate on different kinds of data (polymorphism) is achieved by taking a function pointer to a three-way comparison function, as well as a parameter that specifies the size of its individual input objects. The C standard requires the comparison function to implement a total order on the items in the input array.
A qsort function appears in Version 2 Unix in 1972 as a library assembly language subroutine. Its interface is unlike the modern version, in that it can be pseudo-prototyped as â sorting contiguously-stored -long byte strings from the range [, ). This, and the lack of a replaceable comparison function, makes it unsuitable to properly sort the system's little-endian integers, or any other data structures.
In Version 3 Unix, the interface is extended by calling compar(III), with an interface identical to modern-day . This function may be overridden by the user's program to implement any kind of ordering, in an equivalent fashion to the <code>compar</code> argument to standard (though program-global, of course).
Version 4 Unix adds a C implementation, with an interface equivalent to the standard. It was rewritten in 1983 for the Berkeley Software Distribution. The function was standardized in ANSI C (1989). The assembly implementation is removed in Version 6 Unix.
In 1991, Bell Labs employees observed that AT&T and BSD versions of <code>qsort</code> would consume quadratic time for some simple inputs. Thus Jon Bentley and Douglas McIlroy engineered a new faster and more robust implementation. McIlroy would later produce a more complex quadratic-time input, termed AntiQuicksort, in 1998. This function constructs adversarial data on-the-fly.
The following piece of C code shows how to sort a list of integers using <code>qsort</code>.
Since the comparison function of the original <code>qsort</code> only accepts two pointers, passing in additional parameters (e.g. producing a comparison function that compares by the two value's difference with another value) must be done using global variables. The issue was solved by the BSD and GNU Unix-like systems by introducing a <code>qsort_r</code> function, which allows for an additional parameter to be passed to the comparison function. The two versions of <code>qsort_r</code> have different argument orders. C11 Annex K defines a <code>qsort_s</code> essentially identical to GNU's <code>qsort_r</code>. The macOS and FreeBSD libcs also contain <code>qsort_b</code>, a variant that uses blocks, an analogue to closures, as an alternate solution to the same problem.
In C++, it is faster to use (or <code>std::ranges::sort</code> from C++20 and onwards). Compared to , the templated is more type-safe since it does not require access to data items through unsafe pointers, as does. Also, accesses the comparison function using a function pointer, necessitating large numbers of repeated function calls, whereas in , comparison functions may be inlined into the custom object code generated for a template instantiation. In practice, C++ code using is often considerably faster at sorting simple data like integers than equivalent C code using .