How to efficiently merge k sorted pairwise key/value vectors by keys?-CodePudding

The (Names are duplicated because they are from different parts of the code that call the same functions, and in this case, calls that the std functions make)

This rerun is with 0.5x, it is ~2x faster but now the function consumes 10x more memory than before and you should keep in mind that this values are not generic, they might change depending on what hardware you are running but the proportion are not going to change that much.

Merge of 201500000 (16 bytes) with 100750000 step size Merge operation size 3224.000 mb 1612.000 mb Time taken: 72.062857s

Two other thing you shouldn't forget is that std::vector is dynamic and it's actual size might be bigger and O2 cant really do much optimization to the heap memory access, if you cant make it secuencial then the instruction can only wait.

CodePudding user response：

I barely remember this, but you might find it helpful - I'm pretty sure I have seen merging K sorted linked lists problem. It was using something similar to Divide and Conquer and was close to logarithmic time complexity. I doubt it's any possible to get a better time complexity.

The logic behind this was to minimize iterations over merged lists. If you merge 1st and 2nd lists, then merging it with 3rd involves going through the longer, merged list. This method avoided this by merging all little lists at first, then moving to(what I like to call) '2nd layer merging' by merging 1-time merged lists.

This way, if your lists' length on average is n, you have to do at most logn iterators, resulting in K*log(n) complexity, where K is amount of the lists you have.

Sorry for being a little 'not-so-precise', but I think you might find this piece of information helpful. Although, I'm not familiar with multiway_merge by gnu, so whatever I said might be quite useless too.