AP Computer Science --- Haas --- MergeSort

/**
 * This class performs a merge sort on an array of integers.
 * 
 * Run the following in BlueJ, it works!
 * 
 * Your assignment is to hand in a diagram showing all of the 
 * method calls to "sort" and "merge" for the given data.
 */
public class Mergesort
{
  /**
   * Sort an array of integers from smallest to largest, using a merge sort
   * algorithm.
   */
   public static void sort(int[] data, int first, int n)
   {
      int n1; // Size of the first half of the array
      int n2; // Size of the second half of the array

      if (n > 1) // if array length > 1
      {
         // Compute sizes of the two halves
         n1 = n / 2;
         n2 = n - n1;

         sort(data, first, n1);      // Sort data[first] through data[first+n1-1]
         sort(data, first + n1, n2); // Sort data[first+n1] to the end

         // Merge the two sorted halves.
         merge(data, first, n1, n2);
      }
   } 
   
   private static void merge(int[ ] data, int first, int n1, int n2)
   {
      int[] temp = new int[n1+n2]; // Allocate the temporary array
      int copied  = 0; // Number of elements copied from data to temp
      int copied1 = 0; // Number copied from the first half of data
      int copied2 = 0; // Number copied from the second half of data
      int i;           // Array index to copy from temp back into data

      // Merge elements, copying from two halves of data to the temporary array.
      while ((copied1 < n1) && (copied2 < n2))
      {
         if (data[first + copied1] < data[first + n1 + copied2])
            temp[copied++] = data[first + (copied1++)];
         else
            temp[copied++] = data[first + n1 + (copied2++)];
      }

      // Copy any remaining entries in the left and right subarrays.
      while (copied1 < n1)
         temp[copied++] = data[first + (copied1++)];
      while (copied2 < n2)
         temp[copied++] = data[first + n1 + (copied2++)];

      System.out.print("merge " + first + " " + n1 + " " + n2 + " >>> ");
      // Copy from temp back to the data array.
      for (i = 0; i < n1+n2; i++) {
         data[first + i] = temp[i];
      }
   }
   
   /**
   * The main method illustrates the use of a merge sort to sort a 
   * small array.
   **/
   public static void main(String[] args)
   {
      int i;                      // Array index
      int[] data = {5, 7, 8, 1, 3, 2, 6, 4};

      // Print the array before sorting:
      System.out.print("Before Mergesort: ");
      for (i = 0; i < data.length; i++)
         System.out.print(data[i] + ",");
      System.out.println();

      // Sort the numbers
      sort(data, 0, data.length);

      System.out.print("After Mergesort: ");
      for (i = 0; i < data.length; i++)
         System.out.print(data[i] + ",");
      System.out.println( );
   }
   
}