Back in the summer we had this SO question:
From the article:
How to implement classic sorting algorithms in modern C++?
TheThere are many questions here and on sister sites such as http://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 analyze in terms of correctness and efficiency.
std::sortalgorithm (and its cousins
std::nth_element) from the C++ Standard Library is in most implementations a complicated and hybrid amalgation of more elementary sorting algorithms, such as selection sort, instertion sort, quick sort, merge sort, or heap sort.
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, transparant comparators and polymorphic lambdas
Here are four Live Examples (C++14, C++11, C++98 and Boost, C++98) testing all five algorithms on a variety of inputs (not meant to be exhaustive or rigorous). Just note the huge differences in the LOC: C++11/C++14 need around 120 LOC, C++98 and Boost 180 (+50%) and C++98 more than +100% (note that heap sort could not even be done in terms of standard algorithms).