Return to Answer

There is nothing wrong that I can see.

I can nitpick (so this is only to be over nitpicky). But nothing I say here would stop me from merging this into an existing code base (assuming you had the tests to prove it worked correctly).

1. You template type RandomAccessIterator indicates you only support random access iterators (RAI). If you absolutely want this to be a RAI then maybe you should enforce it? Does std::sort() enforce that fro you? Even if it does is the error messaging a bit obtuse? Ask the question can I help the user of my code spot and diagnose issues more easily if they use it incorrectly?

2. With C++17 std::sort() and std::inplace_merge() support execution policies. Can you work that into your sort? Even if you don't use it yourself can you pass it through to one (or both) of these methods?

3. Find the new return type syntax a bit unnatural still. Personally I only use this when I need to determine the return type at compile time. But don't have anything against it per say.

4. The graph is a bit spikey. I presume that is because of the randomness of the strings you sort. Don't get rid of that but if you supplemented that by assuming one sort is base time and drawing the other two lines as percentage better/worse relative to your reference sort. Does this provide clearer indication of how each sort improves with randomness?

5. Since this is a pretty unique sort. I would add a comment that has a link to the paper describing the sort. Maybe also a ling to any graphs documentation you have written (which could be this page).

There is nothing wrong that I can see.

I can nitpick (so this is only to be overly nitpicky). But nothing I say here would stop me from merging this into an existing code base (assuming you had the tests to prove it worked correctly).

1. Your template type RandomAccessIterator indicates you only support random access iterators (RAI). If you absolutely want this to be a RAI then maybe you should enforce it? Does std::sort() enforce that for you? Even if it does is the error messaging a bit obtuse? Ask the question can I help the user of my code spot and diagnose issues more easily if they use it incorrectly?

2. With C++17 std::sort() and std::inplace_merge() support execution policies. Can you work that into your sort? Even if you don't use it yourself can you pass it through to one (or both) of these methods?

3. Find the new return type syntax a bit unnatural still. Personally I only use this when I need to determine the return type at compile time. But don't have anything against it per say.

4. The graph is a bit spikey. I presume that is because of the randomness of the strings you sort. Don't get rid of that but if you supplemented that by assuming one sort is base time and drawing the other two lines as percentage better/worse relative to your reference sort. Does this provide clearer indication of how each sort improves with randomness?

5. Since this is a pretty unique sort. I would add a comment that has a link to the paper describing the sort. Maybe also a link to any graphs documentation you have written (which could be this page).