Multi merge sort, or when optimizations aren't

In our previous episode we wrote a merge sort implementation that runs a bit faster than the one in stdlibc++. The question then becomes, could it be made even faster. If you go through the relevant literature one potential improvement is to do a multiway merge. That is, instead of merging two arrays into one, you merge four into one using, for example, a priority queue.This seems like a slam dunk for performance.Doubling the number of arrays to merge at a time halves the number of total passes neededThe priority queue has a known static maximum size, so it can be put on the stack, which is guaranteed to be in the cache all the timeProcessing an element takes only log(#lists) comparisonsImplementing multimerge was conceptually straightforward but getting all the gritty details right took a fair bit of time. Once I got it working the end result was slower. And not by a little, either, but more than 30% slower. Trying some optimizations made it a bit faster but not noticeably so.Why is…