sort (C++)

sort is a function in C++ Standard Library that takes two random-access iterators, the start and the end, as arguments and performs a comparison sort on the range of elements between the two iterators, front-inclusive and end-exclusive: [start, end).

The specific sorting algorithm is not mandated and may vary across implementations. However, the worst-case complexity must be O(n log n).^[1]^[2] In previous versions of C++, such as C++03, only average complexity was required to be O(n log n).^[3] 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.^[4] 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×log₂ n, where n is the number of elements, followed by an insertion sort on the result.^[5]

Usage

The sort function is included from the algorithm header of the C++ Standard Library, and carries three arguments: RandomAccessIterator first, RandomAccessIterator last, Compare comp. The third argument has default value - the "less-than" (<) operator to compare elements.

This code sample sorts a given array of integers (in ascending order) and prints it out. Pointers into the array serve as iterators.

#include <iostream>
#include <algorithm>
 
int main() {
  int array[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };
  int elements = sizeof(array) / sizeof(array[0]); 
  std::sort(array, array + elements);
  for (int i = 0; i < elements; ++i) 
     std::cout << array[i] << ' ';
}

The same functionality using vector container:

#include <iostream>
#include <algorithm>
#include <vector>
 
int main() {
  std::vector<int> vec {10, 5, 100};
  std::sort(vec.begin(), vec.end());
  for (int i = 0; i < vec.size(); ++i) 
     std::cout << vec[i] << ' ';
}

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 log² n) – if additional memory is not available, but linearithmic time O(n log n) if additional memory is available.^[6] 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 partial_sort, which sorts N elements from M, with the remaining (M − N) being left in undefined order. Depending on design this may be considerably faster than complete sort.

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 list, provide 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()

sort() can be compared to the qsort() function in the C standard library (in stdlib.h). sort is templated, so it uses the correct comparison function for whatever data type you are sorting, which is already implemented for standard data types. Otherwise you can specify your own comparison function, which can be type-checked by the compiler; whereas for qsort, you must manually cast pointers to the desired type in an unsafe way. Also, qsort accesses the comparison function using a function pointer, necessitating large numbers of repeated function calls, which can take a lot of time; whereas in C++, comparison functions are usually inlined, removing the need for function calls. In practice, C++ code using sort is often many times faster at sorting simple data like integers than equivalent C code using qsort.^[7]

External links

References