Data Structures, Algorithms, & Applications in C++
Chapter 5, Exercise 39

template<class T>
class vectorListWithMerge : public vectorList<T> 
{
   public:
      // constructor and destructor
      vectorListWithMerge(int initialCapacity = 10)
           : vectorList<T> (initialCapacity) {}

      void merge(const vectorListWithMerge<T>& a,
                 const vectorListWithMerge<T>& b);
};

template<class T>
void vectorListWithMerge<T>::merge(const vectorListWithMerge<T>& a,
                                  const vectorListWithMerge<T>& b)
{// Make this the result of merging the sorted lists a and b.
   vector<T>::iterator ia = a.element->begin();  // iterator for a
   vector<T>::iterator aEnd = a.element->end();  
   vector<T>::iterator ib = b.element->begin();  // iterator for b
   vector<T>::iterator bEnd = b.element->end();  

   element = new vector<T>;

   // merge from a and b
   while ((ia < aEnd) && (ib < bEnd))
      if (*ia <= *ib)
      {
         element->push_back(*ia);
         ia++;
      }
      else
      {
         element->push_back(*ib);
         ib++;
      }

   // take care of left overs
   element->insert(element->end(), ia, aEnd);
   element->insert(element->end(), ib, bEnd);
}