The std::sort algorithm (and its cousins std::partial_sort and std::nth_element) from the C++ Standard Library is in most implementations a complicated and hybrid amalgamation of more elementary sorting algorithms, such as selection sort, insertion sort, quick sort, merge sort, or heap sort.
There are many questions here and on sister sites such as https://codereview.stackexchange.com/ related to bugs, complexity and other aspects of implementations of these classic sorting algorithms. Most of the offered implementations consist of raw loops, use index manipulation and concrete types, and are generally non-trivial to analyse in terms of correctness and efficiency.
Question: how can the above mentioned classic sorting algorithms be implemented using modern C++?
- no raw loops, but combining the Standard Library’s algorithmic building blocks from
<algorithm> - iterator interface and use of templates instead of index manipulation and concrete types
- C++14 style, including the full Standard Library, as well as syntactic noise reducers such as
auto, template aliases, transparent comparators and polymorphic lambdas.
Notes:
- for further references on implementations of sorting algorithms see Wikipedia, Rosetta Code or http://www.sorting-algorithms.com/
- according to Sean Parent’s conventions (slide 39), a raw loop is a
for-loop longer than composition of two functions with an operator. Sof(g(x));orf(x); g(x);orf(x) + g(x);are not raw loops, and neither are the loops inselection_sortandinsertion_sortbelow. - I follow Scott Meyers’s terminology to denote the current C++1y already as C++14, and to denote C++98 and C++03 both as C++98, so don’t flame me for that.
- As suggested in the comments by @Mehrdad, I provide four implementations as a Live Example at the end of the answer: C++14, C++11, C++98 and Boost and C++98.
- The answer itself is presented in terms of C++14 only. Where relevant, I denote the syntactic and library differences where the various language versions differ.
