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 ...
Get C++ Coding Standards: 101 Rules, Guidelines, and Best Practices now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.