Sort (C++)

Quality 0.50 · 3 views · Updated 2 months ago

Function for sorting in C++ standard library

title: "Sort (C++)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["c++-standard-library", "sorting-algorithms"] description: "Function for sorting in C++ standard library" topic_path: "technology/algorithms" source: "https://en.wikipedia.org/wiki/Sort_(C++)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Function for sorting in C++ standard library ::

**** is a generic function in the C++ Standard Library for doing comparison sorting. The function originated in the Standard Template Library (STL).

The specific sorting algorithm is not mandated by the language standard and may vary across implementations, but the worst-case asymptotic complexity of the function is specified: a call to must perform no more than O(N log N) comparisons when applied to a range of N elements.

Usage

The function is included from the header of the C++ Standard Library, and carries three arguments: , , . Here, is a templated type that must be a random access iterator, and and must define a sequence of values, i.e., must be reachable from by repeated application of the increment operator to . The third argument, also of a templated type, denotes a comparison predicate. This comparison predicate must define a strict weak ordering on the elements of the sequence to be sorted. The third argument is optional; if not given, the "less-than" ({{code|

This code sample sorts a given array of integers (in ascending order) and prints it out.

::code[lang=cpp] import std;

int main() { int a[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 }; std::sort(std::begin(a), std::end(a)); for (size_t i = 0; i < std::size(a); ++i) { std::print("{} ", a[i]); } std::println(); } ::

The same functionality using a container, using its and methods to obtain iterators:

::code[lang=cpp] import std;

using std::vector;

int main() { vector

Beginning with C++20 and the std::ranges library, sorting can be done over a range.

::code[lang=cpp] import std;

using std::vector;

int main() { vector

Genericity

is specified generically, so that it can work on any random-access container and any way of determining that an element of such a container should be placed before another element .

Although generically specified, is not easily applied to all sorting problems. A particular problem that has been the subject of some study is the following:

  • Let and be two arrays, where there exists some relation between the element and the element for all valid indices .
  • Sort while maintaining the relation with , i.e., apply the same permutation to that sorts .
  • Do the previous without copying the elements of and into a new array of pairs, sorting, and moving the elements back into the original arrays (which would require O(n) temporary space).

A solution to this problem was suggested by A. Williams in 2002, who implemented a custom iterator type for pairs of arrays and analyzed some of the difficulties in correctly implementing such an iterator type. Williams's solution was studied and refined by K. Åhlander.

Complexity and implementations

The C++ standard requires that a call to performs O(N log N) comparisons when applied to a range of N elements. In previous versions of C++, such as C++03, only average complexity was required to be O(N log N). This was to allow the use of algorithms like (median-of-3) quicksort, which are fast in the average case, indeed significantly faster than other algorithms like heap sort with optimal worst-case complexity, and where the worst-case quadratic complexity rarely occurs. The introduction of hybrid algorithms such as introsort allowed both fast average performance and optimal worst-case performance, and thus the complexity requirements were tightened in later standards.

Different implementations use different algorithms. The GNU Standard C++ library, for example, uses a 3-part hybrid sorting algorithm: introsort is performed first (introsort itself being a hybrid of quicksort and heap sort), to a maximum depth given by 2×log2 n, where n is the number of elements, followed by an insertion sort on the result.

Other types of sorting

sort is not stable: equivalent elements that are ordered one way before sorting may be ordered differently after sorting. stable_sort ensures stability of result at expense of worse performance (in some cases), requiring only quasilinear time with exponent 2 – O(n log2 n) – if additional memory is not available, but linearithmic time O(n log n) if additional memory is available. This allows the use of in-place merge sort for in-place stable sorting and regular merge sort for stable sorting with additional memory.

Partial sorting is implemented by , which takes a range of n elements and an integer {{math|m

Selection of the nth element is implemented by nth_element, which actually implements an in-place partial sort: it correctly sorts the nth element, and also ensures that this element partitions so elements before it are less than it, and elements after it are greater than it. There is the requirement that this takes linear time on average, but there is no worst-case requirement; these requirements are exactly met by quickselect, for any choice of pivot strategy.

Some containers, among them std::list (a linked list), provide a specialised version of sort as a member function. This is because linked lists don't have random access (and therefore can't use the regular sort function); and the specialised version also preserves the values list iterators point to.

Comparison to qsort

Aside from , the C++ standard library also includes the function from the C standard library (from ``). 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. "Working Draft, Standard for Programming Language C++". [[International Organization for Standardization.
  2. Williams, Anthony. (2002). "Pairing off iterators". Just Software Solutions.
  3. Åhlander, Krister. (2005). "Sorting Out the Relationships Between Pairs of Iterators, Values, and References".
  4. "Working Draft, Standard for Programming Language C++". [[International Organization for Standardization.
  5. [[International Organization for Standardization. ISO]]/[[International Electrotechnical Commission. IEC]] (2003). ''[[ISO/IEC 14882. ISO/IEC 14882:2003(E): Programming Languages – C++]] §25.3.1.1 sort [lib.sort]'' para. 2
  6. "[http://www.cs.rpi.edu/~musser/gp/algorithms.html Generic Algorithms]", [[David Musser]]
  7. [https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01027.html libstdc++ Documentation: Sorting Algorithm]
  8. [http://en.cppreference.com/w/cpp/algorithm/stable_sort stable_sort]
  9. Martínez, Conrado. (2004). "Partial quicksort".

::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. ::

c++-standard-librarysorting-algorithms