/*
 * Mergesort.java by Richard J. Davies
 * from `Introductory Java for Scientists and Engineers'
 * chapter: `Programming Practices'
 * section: `Example - Mergesort'
 *
 * This program performs mergesort on an array.
 */
public class Mergesort
{
  // The `mergesort' method performs mergesort.
  // It calls itself recursively to sort the
  // subarrays.
  public static int[] mergesort(int[] data)
  {
    if (data.length == 1)
    {
      // If there's only one item then
      // it's already sorted.
      return data;
    }
    else
    {
      // Create two subarrays
      int halflen = data.length/2;

      int[] done = new int[halflen];
      int[] dtwo = new int[data.length - halflen];

      // Copy the data into them
      for (int i=0; i<halflen; i++)
        done[i] = data[i];

      for (int i=halflen; i<data.length; i++)
        dtwo[i-halflen] = data[i];

      // Mergesort the subarrays
      done = mergesort(done);
      dtwo = mergesort(dtwo);

      // Create an array to return
      int[] ans = new int[data.length];

      // Merge the subarrays into it
      int pone = 0;
      int ptwo = 0;
      int pans = 0;

      // Repeat until we've transferred all data.
      while (pans < data.length)
      {
        if (pone < done.length)
        {
          if (ptwo < dtwo.length)
          {
            // If there's data in both arrays,
            // then transfer the lower head
            // to the output list
            if (done[pone] < dtwo[ptwo])
            {
              ans[pans] = done[pone];
              pone++;
            }
            else
            {
              ans[pans] = dtwo[ptwo];
              ptwo++;
            }
          }
          else
          {
            // If there's only data in the first
            // subarray then copy that.
            ans[pans] = done[pone];
            pone++;
          }
        }
        else
        {
          // If there's only data in the second
          // subarray then copy that.
          ans[pans] = dtwo[ptwo];
          ptwo++;
        }

        pans++;
      }

      // return the sorted array.
      return ans;
    }
  }


  // The `main' method actually
  // generates a random array and sorts it.
  public static void main(String[] argv)
  {
    // Pick a size for the array and create it.
    int size = (int) (100 * Math.random());
    int[] data = new int[size];

    // Fill it with elements.
    int i;
    for (i=0; i<size; i++)
      data[i] = (int) (1000 * Math.random());

    // Sort it.
    data = mergesort(data);

    // Print the sorted data.
    for (i=0; i<size; i++)
      System.out.println(data[i]);
  }
}