public class BigOTester_AQKS {
	public void seqTest(Sorter s) {
		
	}
}

interface Sorter {
	public void sort();
	public void changeArray(int[] newArray);
}



/**
This class sorts an array, using the merge sort algorithm.
*/
class MergeSorter implements Sorter
{
/**
   Constructs a merge sorter.
   @param anArray the array to sort
*/
public MergeSorter(int[] anArray)
{
   a = anArray;
}

public void changeArray(int[] newArray) {
	a = newArray;
}

/**
   Sorts the array managed by this merge sorter.
*/
public void sort()
{  
   if (a.length <= 1) return;
   int[] first = new int[a.length / 2];
   int[] second = new int[a.length - first.length];
   System.arraycopy(a, 0, first, 0, first.length);
   System.arraycopy(a, first.length, second, 0, second.length);
   MergeSorter firstSorter = new MergeSorter(first);
   MergeSorter secondSorter = new MergeSorter(second);
   firstSorter.sort();
   secondSorter.sort();
   merge(first, second);
}

/**
   Merges two sorted arrays into the array managed by this
   merge sorter. 
   @param first the first sorted array
   @param second the second sorted array
*/
private void merge(int[] first, int[] second)
{  
   // Merge both halves into the temporary array

   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 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 calls to arraycopy below
   // copies entries

   // Copy any remaining entries of the first array
   System.arraycopy(first, iFirst, a, j, first.length - iFirst);
   
   // Copy any remaining entries of the second half
   System.arraycopy(second, iSecond, a, j, second.length - iSecond);
}

private int[] a;
}


/**
This class sorts an array, using the insertion sort 
algorithm
*/
class InsertionSorter implements Sorter
{
/**
   Constructs an insertion sorter.
   @param anArray the array to sort
*/   
public InsertionSorter(int[] anArray)
{
   a = anArray;
}

/**
   Sorts the array managed by this insertion sorter
*/      
public void sort()
{
   for (int i = 1; i < a.length; i++)
   {
      int next = a[i];
      // Move all larger elements up
      int j = i;
      while (j > 0 && a[j - 1] > next)
      {
         a[j] = a[j - 1];
         j--;
      }
      // Insert the element
      a[j] = next;
   }
}

public void changeArray(int[] newArray) {
	a = newArray;
}

private int[] a;
}


/**
This class sorts an array, using the selection sort 
algorithm
*/
class SelectionSorter implements Sorter
{
/**
   Constructs a selection sorter.
   @param anArray the array to sort
*/
public SelectionSorter(int[] anArray)
{
   a = anArray;
}

/**
   Sorts the array managed by this selection sorter.
*/
public void sort()
{  
   for (int i = 0; i < a.length - 1; i++)
   {  
      int minPos = minimumPosition(i);
      swap(minPos, i);
   }
}

/**
   Finds the smallest element in a tail range of the array.
   @param from the first position in a to compare
   @return the position of the smallest element in the
   range a[from] . . . a[a.length - 1]
*/
private int minimumPosition(int from)
{  
   int minPos = from;
   for (int i = from + 1; i < a.length; i++)
      if (a[i] < a[minPos]) minPos = i;
   return minPos;
}

/**
   Swaps two entries of the array.
   @param i the first position to swap
   @param j the second position to swap
*/
private void swap(int i, int j)
{
   int temp = a[i];
   a[i] = a[j];
   a[j] = temp;
}

public void changeArray(int[] newArray) {
	a = newArray;
}

private int[] a;
}