Problems when size > 2^64

[Morwenn]

A few days ago I had a problem running benchmarks: I realized that everything worked when the size was 10^19 but not when it was 2^20. Apparently 10^19 < 2^64 < 10^20, so there is probably an integer overflow somewhere. I didn't have the time to look at it yet, but I may take a look later.

[terrelln]

If you submit a PR I'll merge it, and if you provide a reproducible test case I'll debug it. Otherwise I'll try to make time to look into it this weekend.

[Morwenn]

I tried to investigate, but realized that I should have had bigger problems sooner, however I ran with NDEBUG when I ran my benchmarks I shared in the other issue, so assert didn't fire while they should have...

In my algorithm I try to choose a pivot at 2/3 of the collection. With a collection of 1,000,000 elements, I run an equivalent of quickselect_adaptive(first, last, first + 666664) (not 666666 because I need a small offset for reasons). I tried to unroll your algorithm:

• First it enters quickselect_adaptive
• 1.0/12.0 < 2/3 < 7.0 / 16.0, so quickselect_adaptive takes the branch that calls repeated_step_left
• At some point repeated_step_left calls quickselect_adaptive again, but the invariants don't hold for some reasons and the assert(first <= k && k < last); fires

If I understand what I read correctly, at this point only first, last and k determine the new values passed to the call to quickselect_adaptive from repeated_step_left; the actual data is the collection doesn't matter. Isn't that a logical bug?