Skip to content

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
int compare(const void* p1, const void* p2)  // comparison function for an array of int
{
  int* a = (int*)p1;
  int* b = (int*)p2;
  if (*a > *b)
    return 1;  // a positive return value means a is greater than b
  else if (*a < *b)
    return -1;  // a negative return value means a is less than b
  else
    return 0;  // a return value of 0 means a and b are equivalent
}

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
struct eg  // example struct
{
  int e;
  int g;
};

// comparison function for an array of struct eg: sort by member e
int compare(const void* p1, const void* p2) {
  struct eg* a = (struct eg*)p1;
  struct eg* b = (struct eg*)p2;
  if (a->e > b->e)
    return 1;  // a positive return value means a is greater than b
  else if (a->e < b->e)
    return -1;  // a negative return value means a is less than b
  else
    return 0;  // a return value of 0 means a and b are equivalent
}

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
// a[0] .. a[n - 1] is the sequence to be sorted
// sort a in place, in ascending order
std::sort(a, a + n);

// cmp is a user-defined comparison function
std::sort(a, a + n, cmp);

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
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, cmp);

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
std::stable_sort(first, last);
std::stable_sort(first, last, cmp);

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
// mid = first + k
std::partial_sort(first, mid, last);
std::partial_sort(first, mid, last, cmp);

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
int a[1009], n = 10;
// ...
std::sort(a + 1, a + 1 + n);                  // sort in ascending order
std::sort(a + 1, a + 1 + n, greater<int>());  // sort in descending order
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
struct data {
  int a, b;

  bool operator<(const data rhs) const {
    return (a == rhs.a) ? (b < rhs.b) : (a < rhs.a);
  }
} da[1009];

bool cmp(const data u1, const data u2) {
  return (u1.a == u2.a) ? (u1.b > u2.b) : (u1.a > u2.a);
}

// ...
std::sort(da + 1, da + 1 + 10);  // use the < operator defined in the struct: ascending order
std::sort(da + 1, da + 1 + 10, cmp);  // compare with the cmp function: descending order

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

References and notes


  1. Because most standard algorithms use operator< for comparison by default. ↩

  2. qsort, qsort_s - cppreference.com ↩