# C++ Cheat Sheet: Built-in Sort Functions

Published Dec 20, 2016Last updated Jan 18, 2017

This tutorial is about different built-in sort functions available in <algorithm> library in C++.

There are different functions available for sorting in C++:

1. std::is_sorted / std::is_sorted_until
2. std::sort
3. std::stable_sort
4. std::partial_sort
5. std::nth_element

We will discuss each one of the above one-by-one :

## 1.std::is_sort / std::is_sorted_until

### A. Syntax

template <typename ForwardIterator>
ForwardIt is_sorted_until(ForwardIterator first, ForwardIterator last);

template<typename ForwardIterator, typename Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

template<typename ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);

template<typename ForwardIterator, typename Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);


### B. Parameters

• first, last: The range of values to examine.
• comp: Functor taking two parameters and returning true if the first argument is less than second.

### C. Return Values

• std::is_sorted: Returns true if all elements in [first, last) is sorted in ascending order.
• std::is_sorted_until: Returns an Iterator it, such that the range [first, it) is largest sorted length from beginning.

### D. Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
int main()
{
std::vector<int> ar = {1, 2, 3, 5, 0};

// clearly, ar is not sorted
assert(not std::is_sorted(ar.begin(), ar.end()));

// {1, 2, 3, 5} is largest possible sorted range
// so std::is_sorted_until will return an iterator pointing to
// element 0 i.e. ar.begin() + 4
assert(std::is_sorted_until(ar.begin(), ar.end()) == ar.begin() + 4);

// lets sort ar
std::sort(ar.begin(), ar.end());

// Now ar is sorted
assert(std::is_sorted(ar.begin(), ar.end()));

// Now ar is sorted to its end
assert(std::is_sorted_until(ar.begin(), ar.end()) == ar.end());

return 0;
}


### E. Complexity

Both std::is_sorted and std::is_sorted_until has the complexity of O(N) where N = std::distance(first, last).

## 2. std::sort

### A. Syntax

template<typename RandomIterator>
void sort(RandomIterator first, RandomIterator last);

template<typename RandomIterator, typename Compare>
void sort(RandomIterator first, RandomIterator last, Compare comp);


### B. Parameters

• first, last: The range of values to sort.
• comp: Functor taking two parameters and returning true if the first argument is less than second.

### C. Return Values

std::sort: Returns nothing. Instead, it just sorts the range [first, last).

### D. Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
int main()
{
std::vector<int> ar = {1, 3, 4, 1, 2, 4, 5, 0};

// ar is not sorted
assert(not std::is_sorted(ar.begin(), ar.end()));

// lets sort ar
std::sort(ar.begin(), ar.end());

// now ar is sorted
assert(std::is_sorted(ar.begin(), ar.end()));

return 0;
}


## 3. std::stable_sort

### A. Syntax

template<typename RandomIterator>
void stable_sort(RandomIterator first, RandomIterator last);

template<typename RandomIterator, typename Compare>
void stable_sort(RandomIterator first, RandomIterator last, Compare comp);


### B. Parameters

• first, last: The range of values to sort.
• comp: Functor taking two parameters and returning true if the first argument is less than second.

### C. Return Values

std::stable_sort: Returns nothing. Instead, it just sorts the range [first, last).

### D. Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
int main()
{
std::vector<int> ar = {1, 3, 4, 1, 2, 4, 5, 0};

// ar is not sorted
assert(not std::is_sorted(ar.begin(), ar.end()));

// lets sort ar
std::stable_sort(ar.begin(), ar.end());

// now ar is sorted
assert(std::is_sorted(ar.begin(), ar.end()));

return 0;
}


### E. Difference between std::sort and std::stable_sort

• In std::stable_sort the order of equal elements are preserved while this is not the case with std::sort.
• Complexity of std::sort is O(N·log(N)) whereas complexity of std::stable_sort is O(N·log(N).log(N)), where N = std::distance(first, last)

## 4. std::partial_sort

### A. Syntax

template<typename RandomIterator>
void partial_sort(RandomIterator first, RandomIterator middle, RandomIterator last);

template<typename RandomIterator, typename Compare>
void partial_sort(RandomIterator first, RandomIterator middle, RandomIterator last, Compare comp);


### B. Parameters

• first, last: The range of values to sort.
• comp: Functor taking two parameters and returning true if the first argument is less than second.

### C. Return Values

std::partial_sort: Returns nothing. Instead, it rearranges elements such that the range [first, middle) contains the sorted middle - first smallest elements in the range [first, last). The order of the remaining elements in the range [middle, last) is unspecified.

### D. Example

#include <iostream>
#include <vector>
#include <algorithm>
void print(std::vector<int> ar)
{
for(auto x : ar) std::cout << x << " ";
std::cout << std::endl;
}
int main()
{
std::vector<int> ar = {1, 3, 7, 1, 2, 4, 5, 0};

// will print 1 3 7 1 2 4 5 0
print(ar);

// mid = 5th element (ar.begin() + 4)
auto mid = ar.begin() + std::distance(ar.begin(), ar.end()) / 2;
// lets partial_sort ar to mid
std::partial_sort(ar.begin(), mid, ar.end());

// will print 0 1 1 2 7 4 5 3
print(ar);

return 0;
}


## 5. std::nth_element

### A. Syntax

template<typename RandomIterator>
void nth_element(RandomIterator first, RandomIterator nth, RandomIterator last);

template<typename RandomIterator, typename Compare>
void nth_element(RandomIterator first, RandomIterator nth, RandomIterator last, Compare comp);


### B. Parameters

• first, last: The range of values to sort.
• comp: Functor taking two parameters and returning true if the first argument is less than second.

### C. Return Values

std::nth_element is a partial sorting algorithm that rearranges elements in [first, last) such that:

• The element pointed at by nth is changed to whatever element would occur in that position if [first, last) was sorted.
• All of the elements before this new nth element are less than or equal to the elements after the new nth element.

### D. Example

#include <iostream>
#include <vector>
#include <algorithm>
void print(std::vector<int> ar)
{
for(auto x : ar) std::cout << x << " ";
std::cout << std::endl;
}
int main()
{
std::vector<int> ar = {1, 3, 6, 1, 2, 4, 7, 0};

// will print 1 3 6 1 2 4 7 0
print(ar);

// mid = 5th element (ar.begin() + 4)
auto mid = ar.begin() + std::distance(ar.begin(), ar.end()) / 2;

// lets nth_element ar to mid
std::nth_element(ar.begin(), mid, ar.end());

// will print 2 0 1 1 3 4 7 6
// mid points to element 3
print(ar);

return 0;
}


## Wrapping Up

So we learned different sorting function available in C++ standard library, which can be useful for various problems. You can also check out other C++ tutorials like A Comprehensive Guide To Singly Linked List Using C++, and this C++ FAQ.