All right, thanks for looking into it, I'll let the question sit a bit more since the bounty ends in 7 days, but if no other, better answers come in, I'll grant it to you.

Thanks for answering, I've extended the question with a confirmation about the test input data. Regarding the auxiliary storage, I consider it not cheating since they do not affect the results of the algorithm, and such optimizations are allowed / encouraged if they can help in achieving better results.

@vvotan, changing the vector<bool> to a vector<char> storage indeed helped, there is a 15-20% improvement in performance, thanks!

@vnp: The random test data that is being generated in the provided code is representative of the actual data being used. On average, there are 3-6 arrays of integers, with the first array always being the largest, and each subsequent one is smaller than the previous. The largest array has around 25000 integers, the next one 15000, then 10000, and it keeps decreasing by a couple thousand with each next array. In-place merge is not mandatory. The only goal is to make the solution faster than the existing ones shown in the code.

One additional note, the creation of the struct is outside the benchmark loop, so the one-time hit's penalty won't be taken into account when measuring the performance. The reason it's a function local static is to use the same test data in all benchmarks within a single benchmarking session, since the data is randomly generated.

Sorry if I wasn't clear enough in the question, and thanks for taking the time to look at it and write an answer. The reason google benchmark code is included is to help potential reviewers easily benchmark the approaches. I am not looking for a code review about whether the code is clean or elegant, I agree it could be cleaner, but it gets through the point of the approaches simply enough. At the moment I'm interested in only making it as fast as possible. Of course i have profiled it many times already, the approaches shown are the result of such profiling / tuning iterations over it.

Apologies and thanks, edited the code to include it.