/**
 *  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
 */

public class MergeSort
{
/**
 * Merge from one array into another
 */
   static void merge (int[] c, int[] 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] <= c[j])  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()

/**
 * Perform one pass through the two arrays, invoking Merge() above
 */
   static void mergePass (int x[], int 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()

/**
 * Entry point for merge sort
 */
   public static void mergeSort (int a[], int n)
   {// Sort a[0:n-1] using merge sort.
      int   s = 1;      // segment size
      int[] b = new int [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

} // end MergeArray class