Слить два линейных списка, сохранив сортировку по возрастанию

#include <iostream>
#include <list>
#include <string>
 
typedef std::list<int> List;
 
void FillList(List& lst)
{
    lst.push_back(3);
    lst.push_back(2);
    lst.push_back(1);
}
 
void PrintList(const List& lst, const std::string& info)
{
    std::cout << info << ": ";
    for (List::const_iterator it = lst.begin(), end = lst.end(); it != end; ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}
 
int main()
{
    List lst1;
    List lst2;
 
    FillList(lst1);
    FillList(lst2);
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "sorting..." << std::endl;
 
    lst1.sort();
    lst2.sort();
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "splicing..." << std::endl;
 
    lst1.splice(lst1.end(), lst2);
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
    std::cout << "###################################" << std::endl;
    std::cout << "sorting..." << std::endl;
 
    lst1.sort();
    lst2.sort();
 
    PrintList(lst1, "lst1");
    PrintList(lst2, "lst2");
 
 
    return 0;
}

#include <ctime>
#include <cstdlib>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
 
// сливает два упорядоченных по возрастанию массива
template <class InputIterator, class OutputIterator>
OutputIterator merge(InputIterator beginA, InputIterator endA, 
  InputIterator beginB, InputIterator endB, OutputIterator inserter) {
  while (true) {
    *inserter++ = (*beginA < *beginB) ? *beginA++ : *beginB++;
    if (beginA == endA) {
      // тут можно return std::copy(beginB, endB, inserter);
      while (beginB != endB) *inserter++ = *beginB++;
      return inserter;
    }
    if (beginB == endB) {
      // тут можно return std::copy(beginA, endA, inserter);
      while (beginA != endA) *inserter++ = *beginA++;
      return inserter;
    }
  }
  return inserter;
};
 
int main(int argc, char **argv) { 
  srand(time(0));
  
  // рандомно генерируются два массива
  int aSize = 10 + rand() % 10;
  int *a = new int[aSize];
  for (int i = 0; i < aSize; ++i) a[i] = rand() % 20;
 
  int bSize = 10 + rand() % 10;
  int *b = new int[bSize];
  for (int i = 0; i < aSize; ++i) b[i] = rand() % 20;
 
  // сортируются
  std::sort(a, a + aSize);
  std::sort(b, b + bSize);
  
  // выводятся на экран
  std::copy(a, a + aSize, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  std::copy(b, b + bSize, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  
  // создается третий массив, в котором будет храниться результат
  int *c = new int[aSize + bSize];
  // слияние
  merge(a, a + aSize, b, b + bSize, c);
  // вывод результата
  std::copy(c, c + aSize + bSize, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  
  delete [] a;
  delete [] b;
  delete [] c;
  return 0;
};