How to implement classic sorting algorithms in modern C++? -- TemplateRex

Back in the summer we had this SO question:

How to implement classic sorting algorithms in modern C++?

by TemplateRex

From the article:

How to implement classic sorting algorithms in modern C++?

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 amalgation of more elementary sorting algorithms, such as selection sort, instertion sort, quick sort, merge sort, or heap sort.

There are many questions here and on sister sites such as 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.

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).


Add a Comment

Comments are closed.

Comments (2)

0 0

TemplateRex said on Jan 1, 2015 01:39 AM:

The Good Answer link is a blatant and verbatim copy (with no updates AFAICS) of my original contribution at Stackoverflow There are many such ad-mining SO rip-offs and it would be appreciated if you updated this post to the SO link!
0 0

Blog Staff said on Jan 5, 2015 06:36 AM:

@TemplateRex: We did start with a link to your original answer, but didn't notice that there was nothing new. We apologize for the error and have now fixed not only the link but also the article attribution. Thank you for your nice explanation of this issue on SO!