merge lists

merge_lists.cpp

//https://news.ycombinator.com/item?id=15804795#15804931
#include <algorithm>
#include <vector>

using intVectors = std::vector<std::vector<int> >;
std::vector<int> mergeLists(intVectors lists)
{
    if (lists.empty()) return {};
    while (lists.size() > 1) {
        intVectors newLists;
        newLists.reserve((lists.size() + 1)/2);
        if (lists.size() % 2) {
            newLists.push_back(std::move(lists.back()));
        }
        for (size_t i = 0; i + 1 < lists.size(); i++) {
            auto &a = lists[i], &b = lists[i+1];
            newLists.emplace_back(a.size() + b.size());
            auto& mergedPair = newLists.back();
            std::merge(a.begin(), a.end(),
                       b.begin(), b.end(),
                       mergedPair.begin());
            newLists.push_back(std::move(mergedPair));
        }
        lists.swap(newLists);
    }
    return std::move(lists[0]);
}