Data Structures, Algorithms, & Applications in Java
Chapter 19, Exercise 17

We begin by making a pass over the input elements and saving the start of each sorted segment in a queue. In a merge pass, we merge pairs of segments. The start points of each of the resulting segments are saved on a queue for use in the next merge pass. Merge passes cease when only one segment remains.

The code is structured in the same way as that for the merge sort described in the text. We have three methods--naturalMergeSort which is the counterpart of MergeSort.mergeSort, naturalMergePass which is the counterpart of MergeSort.mergePass, and merge which is identical to MergeSort.merge. The code is given below. 

public class NaturalMergeSort
{
   // define a queue used for the start positions of sorted segments
   static ArrayQueue queue = new ArrayQueue(10);
   static int numberOfSegments;

   /** sort the elements a[0 : a.length - 1] using
     * the natural merge sort method */
   public static void naturalMergeSort(Comparable [] a)
   {
      if (a.length <= 1)
         // already sorted
         return;

      // define an auxiliary array to faciltate merging
      Comparable [] b = new Comparable [a.length];

      // find the natural segments and save their start positions in a queue
      queue.put(new Integer(0));  // first segment starts at 0
      numberOfSegments = 1;
      for (int i = 1; i < a.length; i++)
         if (a[i - 1].compareTo(a[i]) > 0)
         {// a new segment starts at i
            numberOfSegments++;
            queue.put(new Integer(i));
         }

      while (numberOfSegments > 1)
      {// numberOfSegments is updated by naturalMergePass
         naturalMergePass(a, b); // merge from a to b
         naturalMergePass(b, a); // merge from b to a
      }
   }

   /** merge pairs of adjacent segments from x to y*/
   public static void naturalMergePass(Comparable [] x, Comparable [] y)
   {
      for (int i = 1; i < numberOfSegments; i += 2)
      {// merge two segments
         // find the start and end of the two segments
         Object a = queue.remove();
         int startA = ((Integer) a).intValue();
         int startB = ((Integer) queue.remove()).intValue();
         Object z = queue.getFrontElement();
         int endB = (z == null || ((Integer) z).intValue() == 0) ?
                       x.length - 1 : ((Integer) z).intValue() - 1;
         // merge them 
         merge(x, y, startA, startB - 1, endB);

         // put segment start on queue
         queue.put(a);
      }
   
      // one segment may remain
      if (numberOfSegments % 2 == 1)
      {// copy last segment to y
         Object a = queue.remove();
         int startA = ((Integer) a).intValue();
         for (int i = startA; i < x.length; i++)
            y[i] = x[i];
         queue.put(a);
      }

      // update number of segments
      if (numberOfSegments % 2 == 1)
         numberOfSegments = numberOfSegments / 2 + 1;
      else
         numberOfSegments /= 2;
   }
   
   /** merge c[l:m] and c[m + 1:r] to d[l:r] */
   public static void merge(Comparable [] c, Comparable [] d,
                            int l, int m, int r)
   {
      int i = l,      // cursor for first segment
          j = m + 1,  // cursor for second
          k = l;      // cursor for result
   
      // merge until i or j exits its segment
      while ((i <= m) && (j <= r))
         if (c[i].compareTo(c[j]) <= 0)
            d[k++] = c[i++];
         else
            d[k++] = c[j++];
   
      // take care of left overs
      if (i > m)
         for (int q = j; q <= r; q++)
             d[k++] = c[q];
      else
         for (int q = i; q <= m; q++)
             d[k++] = c[q];
   }
}


Several alternative implementations are possible. For example, we can save the start points of the initial segments in an array-based linear list. The start points for the first merge pass are given by get(i), for i = 0, 1, 2, ...; for the second merge pass, the start points are given by get(i), for i = 0, 2, 4, ...; for the third merge pass, the start points are given by get(i), for i = 0, 4, 8, ...; and so on. This saves the overhead of removing elements from a queue and adding elements to a queue.

Alternatively, we could determine the segment boundaries dynamically and avoid the space overhead of a queue/linear list. The firt segment starts at position 0. We determine the start point of the second segment by scanning the elements from left to right until the element value decreases. Now, we proceed to merge the first two segments. The end of the second segment is determined as the merge of the first two segments progresses. Once the cursor for the second segment encounters a decrease in element value, the second segment has finished. At this time, the start of the third segment becomes known; we scan to the right to find the start of the fourth segment; and then proceed to merge the third and fourth segments. During this merge, we watch for a decrease is value in the fourth segment. This decrease signals the start of the fifth segment. And so on.