Qsort

---

title: "Qsort" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["c-standard-library", "sorting-algorithms"] description: "Standard library function in the C programming language" topic_path: "technology/algorithms" source: "https://en.wikipedia.org/wiki/Qsort" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Standard library function in the C programming language ::

**** 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 (or 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.

History

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 void qsort(void* start, void* end, unsigned int length) – 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 compar 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 qsort 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.

Example

The following piece of C code shows how to sort a list of integers using qsort.

::code[lang=c] #include <stdlib.h>

// Comparison function. Receives two generic (void) pointers to the items under comparison. int compareInts(const void* p, const void* q) { int x = (const int)p; int y = (const int)q;

// Avoid returning x - y, which can cause undefined behaviour
// because of signed integer overflow.
if (x < y) {
    // Return -1 for ascending, +1 for descending order. 
    return -1;
} else if (x > y) {
    // Return +1 for ascending, -1 for descending order.
    return 1;
} else {
    return 0;
}

}

// This could be more concisely written as: int compareInts(const void* p, const void* q) { int x = (const int)p; int y = (const int)q;

return (x > y) - (x < y);

}

// Sort an array of n integers, pointed to by a. void sortInts(int* a, size_t n) { qsort(a, n, sizeof(*a), compareInts); } ::

Extensions

Since the comparison function of the original qsort 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 qsort_r function, which allows for an additional parameter to be passed to the comparison function. The two versions of qsort_r have different argument orders. C11 Annex K defines a qsort_s essentially identical to GNU's qsort_r. The macOS and FreeBSD libcs also contain qsort_b, 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 std::ranges::sort 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 .{{cite book | last = Meyers | first = Scott | author-link = Scott Meyers | title = Effective STL: 50 specific ways to improve your use of the standard template library | publisher = Addison-Wesley | date = 2001 | pages = 203 | isbn = 0-201-74962-9}}

References

References

1. (1993). "Engineering a sort function". Software: Practice and Experience.
2. ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.
3. (June 12, 1972). "UNIX Programmer's Manual, Second Edition". [[Bell_Labs.
4. (February 1973). "UNIX Programmer's Manual, Third Edition". [[Bell_Labs.
5. (November 1973). "UNIX Programmer's Manual, Fourth Edition". [[Bell_Labs.
6. "qsort(III), from UNIX Programmer's Manual, Sixth Edition".
7. (10 April 1999). "A killer adversary for quicksort". Software: Practice and Experience.
8. {{man. 3. qsort_r. FreeBSD

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::