search

Vectorized / Static-Sort

A simple C++ header-only library for fastest sorting of small arrays. Generates sorting networks on compile time via templates.
51 stars 6 forks source link

Lambda possibility? #1

Closed MichaelVoelkel closed 4 years ago

MichaelVoelkel commented 4 years ago

Hi,

thank you for your great repository! This is a really helpful implementation.

I wondered whether you could extend it to a version that also allows lambdas to be used as comparators. In particular, it would be nice to be able to provide a comparator with state/external dependencies to the class. This would make it necessary to pass the lambda type (via decltype) as template argument and the lambda itself as parameter to operator(). Maybe, you have thought about that already?

Vectorized commented 4 years ago

Thank you for the kind words and suggestion!

I've updated the code to take in a less than comparator as the second argument. The comparator can be either const or non-const, in case you want to use a non-const comparator for counting the number of comparisons.

I've also taken the chance to add in a new kind of sort (Tim-Bose-Nelson).

MichaelVoelkel commented 4 years ago

Perfect, thank you a lot! Across your three samples, Tim seems to outperform Bose-Nelson in almost all cases or is at least almost equally good. Is it even substantially slower sometimes? But you seem to recommend Tim anyways, so I will stick to it (and of course, this issue could be also closed)

Vectorized commented 4 years ago

It may be slower than insertion sort if there are 1 or 2 elements that are not in-order. I did experiment using insertion sort instead of the sorting network in such cases, but it somehow ends up being slower than just using the sorting network. It may be due to branch prediction messing things up.

Ok, I'll close the issue.