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

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

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

template<class T>
void arrayListWithMerge<T>::merge(const arrayListWithMerge<T>& a,
                                  const arrayListWithMerge<T>& b)
{// Make this the result of merging the sorted lists a and b.
   int ca = 0;                       // cursor for a
   int cb = 0;                       // cursor for b
   int ct = 0;                       // cursor for this
   // get big enough array for result
   // if you opt to do this only when arrayLength < a.listSize + b.listSize
   // make sure you delete any unneeded elements in original list this.
   delete [] element;
   arrayLength = a.listSize + b.listSize;
   element = new T [arrayLength];

   // merge from a and b
   while ((ca < a.listSize) && (cb < b.listSize))
      if (a.element[ca] <= b.element[cb])
         element[ct++] = a.element[ca++];
      else
         element[ct++] = b.element[cb++];

   // take care of left overs
   copy(a.element + ca, a.element + a.listSize, element + ct);
   ct += a.listSize - ca;
   copy(b.element + cb, b.element + b.listSize, element + ct);
   ct += b.listSize - cb;

   listSize = ct;
}