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

(a)

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

---

/** make this the result of merging the sorted lists a and b */
public void merge(ArrayLinearListWithMerge a,
                  ArrayLinearListWithMerge 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 a.size + b.size > element.length,
   // be sure to set element[a.size + b.size : size] to null
   // to enable garbage collection
   element = new Object [a.size + b.size];

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

   // take care of left overs
   if (ca == a.size)                 // a is finished
      for (int q = cb; q < b.size; q++)
         element[ct++] = b.element[q];
   else
      for (int q = ca; q < a.size; q++)
         element[ct++] = a.element[q];
   size = ct;
}

---

(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 and output can be found in the files ArrayLinearListWithMerge.*.