import java.util.Arrays;
import java.util.Random;

/**
   This program measures the runtime of the merge
   sort algorithm on a sequence of growing arrays.

   For an array of length n, the runtime of merge
   sort is approximately n*lg(n),
       T(n) ~ n*lg(n)
   This is sometimes written as O(n*lg(n)) where
   lg is the logarithm to base 2 function.

   This is quite a bit faster than the O(n^2) of
   selection sort and insertion sort. For large
   numbers n, compare the values of
      n^2
   and
      n*lg(n).
   For example, for n = 1024 = 2^10,
      n^2 = 2^20 = 1,048,576
   but
      n*lg(n) = 1024 * 10 = 10,240.
*/
public class MergeSortProfile
{
   public static void main(String[] args)
   {
      int size = 100_000;   // starting size for the arrays
      int iterations = 10; // how many times to increase the array size

      for (int i = 1; i <= iterations; ++i)
      {
         int[] array = randomIntArray(i*size, 1_000_000);

         long startTime = System.currentTimeMillis();
            MergeSort.sort(array);
         long stopTime = System.currentTimeMillis();
         System.out.println("For n = " + (i*size) + ", time = " + (stopTime - startTime));
      }
   }

   /**
      Creates an array filled with random values.

      @param length the length of the returned array
      @param n the number of possible random values
      @return an array filled with length numbers
              between 0 and n - 1
   */
   public static int[] randomIntArray(int length, int n)
   {
      Random generator = new Random();

      int[] a = new int[length];
      for (int i = 0; i < a.length; ++i)
      {
         a[i] = generator.nextInt(n);
      }
      return a;
   }
}


/**
   The sort method of this class sorts an array,
   using the recursive merge sort algorithm.
*/
class MergeSort
{
   /**
      Sort an array, using merge sort.

      @param a the array to sort
   */
   public static void sort(int[] a)
   {
      if (a.length <= 1) { return; } // base case

      int[] first = new int[a.length / 2];
      int[] second = new int[a.length - first.length];
      // Copy the first half of a into first, the second half into second
      for (int i = 0; i < first.length; ++i)
      {
         first[i] = a[i];
      }
      for (int i = 0; i < second.length; ++i)
      {
         second[i] = a[first.length + i];
      }

      sort(first);   // recursion
      sort(second);  // recursion
      merge(first, second, a);
   }


   /**
      Merge two sorted arrays into a single sorted array.

      @param first the first sorted array
      @param second the second sorted array
      @param a the array into which to merge first and second
   */
   private static void merge(int[] first, int[] second, int[] a)
   {
      int iFirst = 0;   // Next element to consider in the first array
      int iSecond = 0;  // Next element to consider in the second array
      int j = 0;        // Next open position in a

      // As long as neither iFirst nor iSecond is past
      // the end, move the smaller element into a.
      while ( iFirst  < first.length
           && iSecond < second.length )
      {
         if ( first[iFirst] < second[iSecond] )
         {
            a[j] = first[iFirst];
            ++iFirst;
         }
         else
         {
            a[j] = second[iSecond];
            ++iSecond;
         }
         ++j;
      }

      // Note that only one of the two loops below copies entries.
      // Copy any remaining entries of the first array.
      while ( iFirst < first.length )
      {
         a[j] = first[iFirst];
         ++iFirst;
         ++j;
      }
      // Copy any remaining entries of the second half
      while ( iSecond < second.length )
      {
         a[j] = second[iSecond];
         ++iSecond;
         ++j;
      }
   }
}