Sorting in the STL
This page gives a brief introduction to the sorting algorithms implemented in the C and C++ standard libraries.
Unless stated otherwise, the functions listed on this page are defined in the header <algorithm>.
qsort
See: qsort, std::qsort
This is the general-purpose array sorting function of the C standard library, defined in <stdlib.h>; which algorithm it uses is up to the library implementation. In the C++ standard library it is defined in <cstdlib>.
Note2
Although the function is called qsort, neither the C standard nor POSIX requires it to use quicksort, and neither has ever guaranteed any complexity or stability.
Comparison functions for qsort and bsearch
qsort takes four arguments: the name of the array, the number of elements, the size of an element, and the comparison rule. The comparison rule is given as a comparison function; different comparison functions produce different sort orders.
The comparison function must take exactly two parameters of type const void *. Its return value must be a positive number, a negative number or 0.
Here is one way to write a comparison function:
1 2 3 4 5 6 7 8 9 10 11 | |
Note: returning the difference of the two elements instead of a positive or negative number is a classic mistake, because the subtraction can overflow.
Here is an example that sorts structs:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
This example also shows that equivalent does not mean equal: it only means that the two elements are equivalent under this comparison rule.
std::sort
See: std::sort
Usage:
1 2 3 4 5 6 | |
Note: the comparison function of sort returns true or false, and these two values express how two elements compare (which one comes first). Its semantics are completely different from those of qsort's three-way comparison function. For details, see the documentation of sort linked above.
If cmp defines a strict weak ordering, the equivalent three-way comparison rule for qsort should return cmp(a,b) ? -1 : cmp(b,a) ? 1 : 0; it must return zero for equivalent elements.
std::sort is the more commonly used sorting function of the C++ library. Its last argument is a binary comparison function; when no cmp function is given, it sorts in ascending order by default.
Older C++ standards only required its average-case time complexity to be \(O(n\log n)\). C++11 and later standards require its worst-case time complexity to be \(O(n\log n)\).
The C++ standard does not prescribe the algorithm this function uses; the implementation is up to the standard library. For example, the implementations in libstdc++ 14.2.0 and libc++ 20.1.8 both use introsort.
std::nth_element
See: std::nth_element
Usage:
1 2 | |
It rearranges the elements of [first, last) so that the element pointed to by nth becomes the element that would be at that position if [first, last) were sorted. Every element before this new nth element is less than or equal to every element after it.
The implementation is up to the standard library. Common implementations use algorithms such as quickselect or introselect, which after each partition continue only with the side that contains the target position.
For both forms above, the C++ standard requires an average-case time complexity of \(O(n)\), where \(n\) is std::distance(first, last).
It is often used to build a K-D Tree.
std::stable_sort
See: std::stable_sort
Usage:
1 2 | |
A stable sort: equal elements are guaranteed to keep the relative order they had in the original sequence.
It runs in \(O(n\log^2 n)\), or in \(O(n\log n)\) when extra memory is available.
std::partial_sort
See: std::partial_sort
Usage:
1 2 3 | |
It selects the k elements of [first,last) that come first in the order given by cmp and puts them, sorted, into [first,mid); the order of the rest is not guaranteed. When no cmp function is given, it sorts in ascending order by default.
Complexity: about \((\textit{last}-\textit{first})\log(\textit{mid}-\textit{first})\) applications of cmp.
How it works:
The idea of std::partial_sort is as follows. Call make_heap() on the elements in the range [first, mid) of the original container to build a max-heap. Then compare each element of [mid, last) with first, keeping the element at first the maximum of the heap: if the element is less than this maximum, swap the two and adjust the elements of [first, mid) so that they stay in max-heap order. When all the comparisons are done, run the heapsort step sort_heap() on the elements of [first, mid) to put them in increasing order. Note that heap order and increasing order are not the same thing.
Custom comparison
See: operator overloading
For built-in types (such as int) and user-defined structs alike, the comparison function that an STL sorting function uses can be customized: pass a function that implements a binary comparison as the last argument of the call.
Before an STL sorting function can be used on a user-defined struct, the struct must define at least one relational operator, or a binary comparison function must be supplied in the call. Prefer defining operator<.1
Example:
1 2 3 4 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
Strict weak ordering
See also: Applications in C++ - Order Theory
The operator used for sorting must be a strict weak ordering; otherwise the behavior is unpredictable (a runtime error, for example, or a result that is not sorted correctly).
Common mistakes:
- Using
<=to define the less-than operator for sorting. - Having the comparison operator read an external array whose values may change (common in shortest path algorithms).
- Using the result of comparing maxima or minima of several numbers as the comparison operator (the classic mistake in Queen's Game and Processing and Production Scheduling, for example).
External links
References and notes
-
Because most standard algorithms use
operator<for comparison by default. ↩
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, billchenchina, ouuan, NachtgeistW, Enter-tainer, Alisahhh, Great-designer, Ir1d, Xeonacid, ksyx, krn1pnc, Tiphereth-A, caijianhong, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.