Data Structures, Algorithms, & Applications in Java
Chapter 5, Exercise 31

(a)

The merge can be done by examining the elements of the two input lists a and b from the first element to the last. The smaller element is copied into the result list. The member method is given below. The variables ca and cb act as cursors that move through the lists a and b from the first element to the last. ct is a cursor that keeps track of the location for the next element of the result.

public class ArrayCircularListWithMerge
       extends ArrayCircularList
{
   /** make this the result of merging the sorted lists a and b */
   public void merge(ArrayCircularListWithMerge a,
                     ArrayCircularListWithMerge b)
   {
      int ca = a.first;                 // cursor for a
      int cb = b.first;                 // cursor for b
      int ct = 0;                       // cursor for this
      int na = 0;                       // number merged from a
      int nb = 0;                       // number merged from b
      int as = a.size();                // size of a
      int bs = b.size();                // size of b
      // get big enough array for result
      // if you opt to do this only when as + bs > element.length,
      // be sure to set relevant positions of element to null
      // to enable garbage collection
      element = new Object [as + bs];

      // merge from a and b
      while ((na < as) && (nb < bs))
         if (((Comparable) a.element[ca]).compareTo(b.element[cb]) <= 0)
         {// merge from a
            element[ct++] = a.element[ca];
            ca = (ca + 1) % a.element.length;
            na++;
         }
         else
         {// merge from b
            element[ct++] = b.element[cb];
            cb = (cb + 1) % b.element.length;
            nb++;
         }
   
      // take care of left overs
      if (na == a.size())                 // a is finished
         for (int q = nb; q < bs; q++)
         {
            element[ct++] = b.element[cb];
            cb = (cb + 1) % b.element.length;
         }
      else  // b is finished
         for (int q = na; q < as; q++)
         {
            element[ct++] = a.element[ca];
            ca = (ca + 1) % a.element.length;
         }
      first = 0;
      last = ct - 1;
   }
}

(b)

In each iteration of the while loop the value of ct increases by one. On exiting this loop, ct < a.size + b.size. The time spent in the for loops is either O(a.size) or O(b.size). So, the complexity is O(a.size + b.size).

(c)

The test program is given as the method dataStructures.ArrayCircularList.main. The output is in the file ArrayCircularList.output.