слить три отсортированных файла

Для трёх последовательностей, работает простейший алгоритм:

• выводим минимум из текущих трёх значений и сдвигаем последовательность, содержащую минимум
• если любая из последовательностей закончилась, то используем алгоритм для двух последовательностей

#include <algorithm> // merge
template <class It, class OutIt> // InputIterator, OutputIterator
OutIt merge3(It afirst, It aend, It bfirst, It bend, It cfirst, It cend,
             OutIt out)
{
  for ( ; ; ) {
    if (afirst == aend)
      return std::merge(bfirst, bend, cfirst, cend, out);
    else if (bfirst == bend)
      return std::merge(afirst, aend, cfirst, cend, out);
    else if (cfirst == cend)
      return std::merge(afirst, aend, bfirst, bend, out);
    auto a = *afirst, b = *bfirst, c = *cfirst;
    if (a < b) {
      if (a < c) {
        *out++ = a; // a < b && a < c i.e., a == min(a, b, c)
        ++afirst;
      } else {
        *out++ = c; // a < b && !(a < c) i.e.,  b > a >= c
        ++cfirst;
      }
    } else if (b < c) {
        *out++ = b; // !(a < b) && b < c i.e., a >= b && c > b
        ++bfirst;
    } else {
        *out++ = c; //  !(a < b) && !(b < c) i.e., a >= b >= c
        ++cfirst;
    }
  }
}

К примеру, чтобы объединить отсортированные последовательности чисел из файлов a, b, c:

#include <iostream>  // cout
#include <iterator>  
#include <fstream>   // ifstream
int main()
{
  std::ifstream afile("a"), bfile("b"), cfile("c");
  typedef std::istream_iterator<int> It;
  merge3(It(afile), It(), It(bfile), It(), It(cfile), It(),
         std::ostream_iterator<int>(std::cout, "\n"));
}

Чтобы объединить отсортированные строки:

#include <cstring>
#include <iostream>
#include <iterator>
#include "merge.hpp"
int main()
{
  const char* a[] = {"aabbc", "bcdd", "acdfff"};
  merge3(a[0], a[0] + std::strlen(a[0]),
         a[1], a[1] + std::strlen(a[1]),
         a[2], a[2] + std::strlen(a[2]),
         std::ostream_iterator<char>(std::cout, " "));
}

Результат:

a a a b b b c c c d d d f f f

Чтобы поместить результат в строку, вместо вывода на экран, можно std::back_inserter(s) использовать (где s это std::string) вместо ostream_iterator<>():

#include <iostream>
#include <iterator>
#include <string>
int main()
{
  using namespace std;
  string a[] = {"aabbc", "bcdd", "acdfff"};
  string s;
  merge3(begin(a[0]), end(a[0]),
         begin(a[1]), end(a[1]),
         begin(a[2]), end(a[2]),
         back_inserter(s));
  cout << s;
}

Результат:

aaabbbcccdddfff

mergek() — объединение k сортированных последовательностей

Чтобы поддерживать произвольное количество файлов k, можно использовать кучу (heap), чтобы для каждого элемента не приходилось бы каждый раз ~k сравнений производить, чтобы новый минимум найти:

template <class MinHeap, class OutIt>
OutIt mergek(MinHeap& heap, OutIt out)
{
  while(!heap.empty()) {
    auto range = heap.top(); // pop minimum in O(1)
    heap.pop();
    *out++ = *range.first++; // output the minimum, move input
    if (range.first != range.second) // push unless empty range
      heap.emplace(range); // find new minimum in O(log k)
  }
  return out;
}

До тех пор пока есть последовательности в куче (в виде пары итераторов, указывающих на первый и за последний элемент соответственно):

1. выбирается последовательность из кучи, соответствующая минимальному элементу
2. выводится в результат и соответствующая позиция в последовательности сдвигается
3. сдвинутая позиция добавляется назад в кучу, чтобы новый минимум найти.
4. повтор

Смысл использования heap в том, что используется порядка O(log k) сравнений вместо O(k), если просто набор k последовательностей хранить (log10(1000000) == 6 так что O(log k) значительно лучше чем O(k) для достаточно большого k).

К примеру, чтобы объединить произвольное число файлов заданных в командной строке:

#include <fstream>
#include <iostream>
#include <iterator>
#include <queue>
#include <vector>
int main(int argc, char *argv[])
{
  using namespace std;
  // input files are streams (iterators) of ints here
  typedef istream_iterator<int> It;
  // the heap contains pairs of iterators over files: (current_position, eof)
  typedef pair<It, It> Range;
  auto greater_first = [](Range lhs, Range rhs) {
    return *lhs.first > *rhs.first; 
  };
  priority_queue<Range, vector<Range>, decltype(greater_first)>
    heap(greater_first);
  ifstream file[argc]; //NOTE: dummy file[0]
  while (--argc) {
    file[argc].open(argv[argc]); //NOTE: ignore errors
    heap.emplace(It(file[argc]), It());
  }
  mergek(heap, ostream_iterator<int>(cout, "\n"));
}

Пример запуска:

$ ./merge-k a b c

Каждый входной файл, как и в случае merge3(), представлен как пара итераторов: (current_position, eof). Эти пары заносятся в кучу (priority_queue<>), чтобы можно было бы быстро минимум находить среди текущих позиций во всех файлах. Сравнение происходит с помощью greater_first() функции (используется > операция, так как по умолчанию priority_queue<> возвращает наибольший элемент, а мы хотим минимум найти).

Открыть все три и прочитать первые токены. Найдя среди них минимальный, сбросить его в выход и подчитать из этого файла следующий. Повторять, пока все файлы не закончатся.

Ну точно так, как я вам уже отвечал на предыдущий вопрос:

#include <vector>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <limits>
#include <algorithm>
using namespace std;
void makeFile(const char * name)
{
    ofstream out(name);
    int curval = rand()%100;
    for(int j = 0; j < 10000+rand()%100; ++j)
    {
        out << curval << "\n";
        curval += rand()%100;
    }
}
struct Get
{
    int val;
    ifstream* f;
};
int main(int argc, const char * argv[])
{
    makeFile("data1");  // Создали три отсортированных файла
    makeFile("data2");
    makeFile("data3");
    vector<Get> ps;        // Вектор структуры с последним считанным значением и указателем, откуда читаем
    ifstream in1("data1");
    ifstream in2("data2");
    ifstream in3("data3");
    int x;
    in1 >> x;                // Читаем из первого файла
    ps.push_back({x,&in1});  // и вносим в вектор файлов
    in2 >> x;                // Читаем из второго файла
    ps.push_back({x,&in2});  // и вносим в вектор файлов
    in3 >> x;                // Читаем из третьего файла
    ps.push_back({x,&in3});  // и вносим в вектор файлов
    ofstream out("sort");    // Выходной файл
    for(;ps.size();)         // Пока есть какие-то данные (что читать)
    {                        // Находим минимальный элемент из трех фвйлов
        auto g = min_element(ps.begin(), ps.end(),
                             [](const Get&g1, const Get&g2) { return g1.val < g2.val; });
        out << g->val << "\n";    // Выводим его в новый файл
        if (!((*g->f) >> g->val)) // Читаем из файла, откуда был взят элемент, новый элемент
        {                         // Если не удалось (конец файла)
            ps.erase(g);          // Выбрасываем этот файл из рассмотрения
        }
    }
}