home | help 
std::sort(3)		       C++ Standard Libary		    std::sort(3)

NAME
     std::sort - std::sort

Synopsis
	Defined in header <algorithm>
	template<  class RandomIt >				  (1) (constexpr
     since C++20)
	void sort( RandomIt first, RandomIt last );
	template< class ExecutionPolicy, class RandomIt >

	void  sort(  ExecutionPolicy&&	policy, 		     (2)  (since
     C++17)

		   RandomIt first, RandomIt last );
	template< class RandomIt, class Compare >
	void  sort( RandomIt first, RandomIt last, Compare comp   (3) (constexpr
     since C++20)
	);
	template< class ExecutionPolicy, class RandomIt, class
	Compare >

	void  sort(  ExecutionPolicy&&	policy, 		     (4)  (since
     C++17)

		   RandomIt first, RandomIt last, Compare comp
	);

	Sorts  the  elements in the range [first, last) in non-descending order.
     The order of
	equal elements is not guaranteed to be preserved.

	1) Elements are sorted with respect to
	operator<
	(until C++20)
	std::less{}
	(since C++20).
	3) Elements are sorted with respect to comp.
	2,4) Same as (1,3), but executed according to policy.
	These overloads participate in overload resolution only if

	std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>    is    true.
     (until
										  C++20)
	std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>      is
     true. (since
										  C++20)

	If any of the following conditions is satisfied, the behavior  is  unde-
     fined:

	  * The type of *first is not Swappable.	   (until C++11)
	  * RandomIt is not ValueSwappable.
	  * The type of *first is not MoveConstructible.   (since C++11)
	  * The type of *first is not MoveAssignable.

Parameters
	first, last -  the range of elements to sort
	policy	    -  the execution policy to use. See execution policy for de-
     tails.
		       comparison function object (i.e. an object that satisfies
     the
		       requirements  of Compare) which returns true if the first
     argument is
		       less than (i.e. is ordered before) the second.

		       The signature of the comparison function should be equiv-
     alent to the
		       following:

		       bool cmp(const Type1& a, const Type2& b);
	comp	    -
		       While the signature does not need  to  have  const&,  the
     function must
		       not  modify  the objects passed to it and must be able to
     accept all
		       values of type (possibly const) Type1 and  Type2  regard-
     less of value
		       category (thus, Type1& is not allowed
		       , nor is Type1 unless for Type1 a move is equivalent to a
     copy
		       (since C++11)).
		       The  types Type1 and Type2 must be such that an object of
     type
		       RandomIt can be dereferenced  and  then	implicitly  con-
     verted to both of
		       them.

Type requirements
	-
	RandomIt must meet the requirements of LegacyRandomAccessIterator.
	-
	Compare must meet the requirements of Compare.

Complexity
	Given \(\scriptsize N\)N as last - first:

	1,2) \(\scriptsize O(N \cdot \log(N))\)O(NA.log(N)) comparisons using
	operator<
	(until C++20)
	std::less{}
	(since C++20).
	3,4)  \(\scriptsize O(N \cdot \log(N))\)O(NA.log(N)) applications of the
     comparator
	comp.

Exceptions
	The overloads with a template parameter named ExecutionPolicy report er-
     rors as
	follows:

	  * If execution of a function invoked as part of the  algorithm  throws
     an exception
	    and  ExecutionPolicy is one of the standard policies, std::terminate
     is called.
	    For any other ExecutionPolicy, the	behavior  is  implementation-de-
     fined.
	  * If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation
	See also the implementations in libstdc++ and libc++.

Notes
	Before	LWG713,  the  complexity requirement allowed sort() to be imple-
     mented using
	only Quicksort, which may need \(\scriptsize O(N^2)\)O(N2
	) comparisons in the worst case.

	Introsort  can	handle	all   cases   with   \(\scriptsize   O(N   \cdot
     \log(N))\)O(NA.log(N))
	comparisons (without incurring additional overhead in the average case),
     and thus is
	usually used for implementing sort().

	libc++ has not implemented the corrected time complexity requirement un-
     til LLVM 14.

Example
     // Run this code

      #include <algorithm>
      #include <array>
      #include <functional>
      #include <iostream>
      #include <string_view>

      int main()
      {
	  std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

	  auto print = [&s](std::string_view const rem)
	  {
	      for (auto a : s)
		  std::cout << a << ' ';
	      std::cout << ": " << rem << '\n';
	  };

	  std::sort(s.begin(), s.end());
	  print("sorted with the default operator<");

	  std::sort(s.begin(), s.end(), std::greater<int>());
	  print("sorted with the standard library compare function object");

	  struct
	  {
	      bool operator()(int a, int b) const { return a < b; }
	  }
	  customLess;

	  std::sort(s.begin(), s.end(), customLess);
	  print("sorted with a custom function object");

	  std::sort(s.begin(), s.end(), [](int a, int b)
					{
					    return a > b;
					});
	  print("sorted with a lambda expression");
      }

Output:
      0 1 2 3 4 5 6 7 8 9 : sorted with the default operator<
      9  8  7  6 5 4 3 2 1 0 : sorted with the standard library compare function
     object
      0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object
      9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression

	Defect reports

	The following behavior-changing defect	reports  were  applied	retroac-
     tively to
	previously published C++ standards.

	  DR	 Applied to		Behavior as published		    Cor-
     rect behavior
			   the \(\scriptsize O(N \cdot			  it  is
     required for
	LWG  713  C++98      \log(N))\)O(NA.log(N)) time complexity was only the
     worst case
			   required on the average

See also
	partial_sort sorts the first N elements of a range
		     (function template)
	stable_sort  sorts a range of elements while  preserving  order  between
     equal elements
		     (function template)
	ranges::sort sorts a range into ascending order
	(C++20)      (niebloid)

http://cppreference.com 	   2024.06.10			    std::sort(3)
home | help