/**
 *  Iterative merge sort algorithm --- as a static method

 *  @author:  Sartaj Sahni, ported to Java by Timothy Rolfe

 *  @see  Data Structures, Algorithms, and Applications in C++,
 *        pp. 680-81 (the original in C++ has a memory leak, but
 *        that is not a problem in Java due to garbage collection)

 *  Minor revision by Timothy Rolfe (tjr) --- saves two comparisons
 */

class MergeArray
{
/**
 * Entry point for merge sort
 */
   static void mergeSort (Comparable a[], int n)
   {
   // Sort a[0:n-1] using merge sort.
      int           s = 1;   // segment size
      Comparable [] b = new Comparable [n];

      while (s < n)
      {  mergePass (a, b, s, n); // merge from a to b
         s += s;                 // double the segment size
         mergePass (b, a, s, n); // merge from b to a
         s += s;                 // again, double the segment size
      } // end while
      // in C/C++, return the scratch array b by free/delete  --- tjr
   }  // end mergeSort

/**
 * Perform one pass through the two arrays, invoking Merge() above
 */
   static void mergePass (Comparable x[], Comparable y[], int s, int n)
   {
   // Merge adjacent segments of size s.
      int i = 0;

      while (i <= n - 2 * s)
      {//Merge two adjacent segments of size s
         merge (x, y, i, i+s-1, i+2*s-1);
         i = i + 2*s;
      }
   // fewer than 2s elements remain
      if (i + s < n)
         merge (x, y, i, i+s-1, n-1);
      else
         for (int j = i; j <= n-1; j++)
            y[j] = x[j];   // copy last segment to y
   } // end mergePass()

/**
 * Merge from one array into another
 */
   static void merge (Comparable[] c, Comparable[] d, int lt, int md, int rt)
   {
   // Merge c[lt:md] and c[md+1:rt] to d[lt:rt]
      int i = lt,       // cursor for first segment
          j = md+1,     // cursor for second
          k = lt;       // cursor for result

   // merge until i or j exits its segment
      while ( (i <= md) && (j <= rt) )
         if (c[i].compareTo(c[j]) <= 0)  d[k++] = c[i++];
         else                            d[k++] = c[j++];

   // take care of left overs --- tjr code:  only one while loop actually runs
      while ( i <= md )
         d[k++] = c[i++];
      while ( j <= rt )
         d[k++] = c[j++];
   } // end merge()

} // end MergeArray class