Слияние k отсортированных массивов: два указателя или куча — что выбрать?

Для двух массивов — да, два указателя за O(n + m): идём по обоим, на каждом шаге берём меньший текущий элемент.

Для k массивов наивное «сливать первый со вторым, результат с третьим...» даёт O(N * k), где N — суммарное число элементов: каждый элемент копируется до k раз. Лучше — куча (min-heap) на k указателей. Держим в куче по одному текущему элементу из каждого массива; извлекаем минимум, кладём в результат, продвигаем указатель в том массиве и пушим его новый элемент.

struct Node { int val, arr, idx; };
struct Cmp { bool operator()(const Node& a, const Node& b){ return a.val > b.val; } };

vector<int> mergeK(const vector<vector<int>>& v) {
    priority_queue<Node, vector<Node>, Cmp> pq;
    for (int i = 0; i < (int)v.size(); i++)
        if (!v[i].empty()) pq.push({v[i][0], i, 0});
    vector<int> res;
    while (!pq.empty()) {
        Node t = pq.top(); pq.pop();
        res.push_back(t.val);
        if (t.idx + 1 < (int)v[t.arr].size())
            pq.push({v[t.arr][t.idx + 1], t.arr, t.idx + 1});
    }
    return res;
}

Сложность O(N log k): каждый из N элементов один раз входит и выходит из кучи размера ≤ k. Память O(k) на кучу + O(N) на результат. Это лучше, чем наивные O(N*k) и чем «слить всё и отсортировать» O(N log N) (т.к. log k ≤ log N).