L>    while(!heap.empty()) {
L>        auto item = heap.top();
L>        auto point = get<0>(item);
L>        int index = get<1>(item);
L>        out_iter->put(caller, point.value, page);
L>        heap.pop();
L>        if (iter[index] != ends[index]) {
L>            auto point = *iter[index];
L>            iter[index]++;
L>            heap.push(make_tuple(point, index));
L>        }
L>    }
L>

while(!q.empty())
{
    auto range = heap.top();  
    q.pop();

    //assert(!empty(range));
    *out++ = *begin(range);
    range = make_iterator_range(next(begin(range)), end(range));
    if(!empty(range))
        q.push(range);
}

while(!q.empty())
{
    auto range = heap.top();  
    q.pop();
    if(!q.empty())
    {
        auto ceiling = *begin(heap.top());
        auto last = upper_bound(range, ceiling); // can be linear or binary search
        copy(begin(range), last, out)

        range = make_iterator_range(last, end(range));
        if(!empty(range))
            q.push(range);
    }
    else
    {
        copy(range, out);
    }
}

struct RangeGroup {
    size_t size;
    vector<vector<double> > rs;
    vector<size_t> ps;

    void reset() {
        for (size_t i = 0; i < ps.size(); i++)
            ps[i] = 0;
    }

    double get_next(size_t i) {
        assert (i < rs.size());
        double res = INF;
        if (ps[i] < rs[i].size()) {
            res = rs[i][ps[i]];
            ps[i]++;
        }
        return res;
    }

    void init_random(size_t n, size_t m) {
        size = n * m;
        rs.resize(n);
        ps.resize(n);
        for (unsigned int i = 0; i < n; i++) {
            rs[i].resize(m);
            for (unsigned j = 0; j < m; j++)
                rs[i][j] = drand48();
            std::stable_sort(&rs[i][0], &rs[i][m]);
        }
    }

    void init_good(size_t n, size_t m) {
        size = n * m;
        double rsize = 1.0 / size;
        rs.resize(n);
        ps.resize(n);
        for (unsigned int i = 0; i < n; i++) {
            rs[i].resize(m);
            for (unsigned j = 0; j < m; j++)
                rs[i][j] = (i * m + j) * rsize;
        }
    }

    void init_bad(size_t n, size_t m) {
        size = n * m;
        double rsize = 1.0 / size;
        rs.resize(n);
        ps.resize(n);
        for (unsigned int i = 0; i < n; i++) {
            rs[i].resize(m);
            for (unsigned j = 0; j < m; j++)
                rs[i][j] = (i + j * n) * rsize;
        }
    }

};


class MergerHeap
{
    struct Node {
        double v;
        unsigned int idx, fill;
    };

    vector<Node> nodes;

    void drawn_node(unsigned int i, unsigned int n)
    {
        assert (i < n);
        double v = nodes[i].v;
        unsigned int idx = nodes[i].idx;

        for (;;) {
            unsigned int ic = 2 * i + 1;
            if (ic >= n)
                break;
            ic += (nodes[ic].v > nodes[ic + 1].v);
            if (v <= nodes[ic].v)
                break;
            nodes[i] = nodes[ic];
            i = ic;
        }

        nodes[i].v = v;
        nodes[i].idx = idx;
    }


    void heapify()
    {
        unsigned int n = nodes.size() - 1;
        for (unsigned int i = n; i > 0;) {
            drawn_node(--i, n);
        }
    }

public:
    void merge(RangeGroup *rg, double *dst)
    {
        unsigned int n = rg->rs.size();
        rg->reset();
        assert (n >= 2);
        nodes.resize(n + 1);
        nodes[n].v = INF;
        nodes[n].idx = ~0;
        for (unsigned int i = 0; i < n; i++) {
            nodes[i].idx = i;
            nodes[i].v = rg->get_next(i);
        }

        heapify();

        for (;;) {
            unsigned int ic = 1 + (nodes[1].v > nodes[2].v);
            double v = nodes[0].v;
            unsigned int idx = nodes[0].idx;
            double nv = nodes[ic].v;

            for (;;) {
                if (v == INF)
                    return;
                *dst++ = v;
                v = rg->get_next(idx);
                if (v > nv)
                    break;
            }

            unsigned int i = 0;
            nodes[0].v = nv;
            nodes[0].idx = nodes[ic].idx;
            i = ic;
            for (;;) {
                ic = 2 * i + 1;
                if (ic >= n)
                    break;
                ic += (nodes[ic].v > nodes[ic + 1].v);
                if (v <= nodes[ic].v)
                    break;
                nodes[i].v = nodes[ic].v;
                nodes[i].idx = nodes[ic].idx;
                i = ic;
            }

            nodes[i].v = v;
            nodes[i].idx = idx;
        }
    }
};

К>0 -\___ n+1 _
К>1 -/         \___ n+n/2+1 ___
К>2 -\___ n+2 _/               \
К>3 -/
К>...                           ..... ___ 2n-1
К>    ___ n+n/2
К>n -/

binary merge 25.59
K-way merge 19.91

C>Основной подвох, видимо, в том, что Вы не резервируете память для добавления бак-инсерторами, это самая верхняя функция merge для бинарного слияния и main для очереди. Отсутствие предварительного резервирования, при стандартном алгоритме удвоения, может приводить к увеличению времени в 2-3 раза для критичных по памяти приложений и к существенному увеличению пикового потребления памяти. После добавления резервирования в этих двух местах имеем на сервере 7 и 16.25 секунд соответственно. Искомой тройки ещё нет

zsh 1056 % perf stat  -e dTLB-load-misses,iTLB-load-misses ./fill_test
binary merge 13.01

 Performance counter stats for './fill_test':

        41,931,880 dTLB-load-misses                                            
            48,332 iTLB-load-misses                                            

      17.169628482 seconds time elapsed

zsh 1057 % perf stat  -e dTLB-load-misses,iTLB-load-misses ./fill_test
K-way merge 20.33

 Performance counter stats for './fill_test':

       290,434,271 dTLB-load-misses                                            
            90,818 iTLB-load-misses                                            

      24.871572710 seconds time elapsed

zsh 1062 % perf stat  -e cache-misses ./fill_test
binary merge 12.77

 Performance counter stats for './fill_test':

        44,452,101 cache-misses                                                

      16.894329776 seconds time elapsed

zsh 1061 % perf stat  -e cache-misses ./fill_test
K-way merge 20.2

 Performance counter stats for './fill_test':

        28,456,613 cache-misses                                                

      24.533016829 seconds time elapsed

    for (unsigned int i = 0; i < NUM_WAYS; i++) {
        ds[i].resize(LEN_WAYS);
        for (unsigned int j = 0; j < LEN_WAYS; j++)
            ds[i][j] = std::make_tuple(j * NUM_WAYS + i, 0);
    }

C>Начали, но не везде Не уверен насчёт очереди, но в генераторе данных похоже ничего не резервируете, и по-прежнему заполняете данные поперёк памяти, о чём говорят уходящие туда 4 с лишним секунды. Отсутствие резервирования не только ухудшает производительность этого куска (в которой Вы и не заинтересованы), увеличивает пиковое потребление памяти и затрудняет профилирование, но и приводит к фрагментации памяти, которая непредсказуемым образом влияет на производительность слияний, что при тестировании совсем некстати.

C>    for (unsigned int i = 0; i < NUM_WAYS; i++) {
C>        ds[i].resize(LEN_WAYS);
C>        for (unsigned int j = 0; j < LEN_WAYS; j++)
C>            ds[i][j] = std::make_tuple(j * NUM_WAYS + i, 0);
C>    }
C>

binary merge 12.53

 Performance counter stats for './fill_test':

        32,974,456 dTLB-load-misses                                            
        33,419,552 cache-misses                                                

      13.752300615 seconds time elapsed

K-way merge 20.07

 Performance counter stats for './fill_test':

       279,699,671 dTLB-load-misses                                            
        15,369,581 cache-misses                                                

      21.386986439 seconds time elapsed

MergerHeap 9.05

 Performance counter stats for './fill_test':

       159,302,104 dTLB-load-misses                                            
        20,355,224 cache-misses                                                

      11.211531765 seconds time elapsed