C++ Coding Standards: 101 Rules, Guidelines, and Best Practices

86. Use the right STL sort algorithm

Summary

Sort “just enough:” Understand what each of the sorting algorithms does, and use the cheapest algorithm that does what you need.

Discussion

You don’t always need a full sort; you usually need less, and rarely you need more. In general order from cheapest to most expensive, your standard sorting algorithm options are: partition, stable_partition, nth_element, partial_sort (with its variant partial_sort_copy), sort, and stable_sort. Use the least expensive one that does the work you actually need; using a more powerful one is wasteful.

partition, stable_partition, and nth_element run in linear time, which is nice.

nth_element, partial_sort, sort, and stable_sort require random-access iterators. You ...