public class Sort {

    public static int randInt (int low, int high) {
	while (true) {
	    int x = (int)(Math.random() * (high-low+1) + low);
	    if (x >= low && x <= high) return x;
	} 
    }

    // selectionSort: this is the simple selection sort
    public static int[] selectionSort (int[] a) {
	for (int i=0; i<a.length; i++) {
	    int j = findHighest (a, i, a.length-1);
	    swapElements (a, i, j);
	}
	return a;
    }

    // swapElements: swaps the references to the elements, not the
    // contents of the elements
    public static void swapElements (int[] a, int i, int j) {
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
    }

    // findHighestElement: traverses the given index range of the
    // array and finds the element with the highest rank
    public static int findHighest (int[] a, int low, int high) {
	int winner = low;
	for (int i=low+1; i<=high; i++) {
	    if (a[i] > a[winner]) {
		winner = i;
	    }
	}
	return winner;
    }

    // subarray: returns a new array with a copy of the elements
    // in the range low to high, including both
    public static int[] subarray (int[] a, int low, int high) {
	int[] sub = new int[high-low+1];
	for (int i = 0; i<sub.length; i++) {
	    sub[i] = a[low+i];
	}
	return sub;
    }

    // merge: takes two arrays and merges them into a new array.
    // precondition--the old arrays must be sorted
    public static int[] merge (int[] a1, int[] a2) {
	// create the new array
	int[] result = new int[a1.length + a2.length];
		
	int i = 0;     // traverses the first input array
	int j = 0;     // traverses the second input array
		
	// k traverses the new (merged) array
	for (int k = 0; k<result.length; k++) {
			
	    // if a1 is empty, a2 wins; if a2 is empty, a1 wins; otherwise,
	    // compare the two elements
	    if (i == a1.length || j != a2.length && a2[j] > a1[i]) {
		result[k] = a2[j];  j++;
	    } else {
		result[k] = a1[i];  i++;
	    }
	}
	return result;
    }

    // mergeSort: takes a array of elements and returns a new array that
    // contains references to to the same set of elements, but in order
    public static int[] mergeSort (int[] a) {
	// base case is a array with one element
	if (a.length == 1) return a;
	
	// divide the array roughly in half
	int mid = a.length / 2;
	int[] a1 = subarray (a, 0, mid-1);
	int[] a2 = subarray (a, mid, a.length-1);
	
	// sort the halves 
	a1 = mergeSort (a1);
	a2 = mergeSort (a2);
		
	// merge the two halves and return the result
	// (a1 and a2 get garbage collected)
	return merge (a1, a2);
    }

    public static int[] heapSort (int[] a) {
	Heap heap = new Heap ();
	for (int i = 0; i<a.length; i++) {
	    heap.insert (new Integer (a[i]));
	}
	for (int i = 0; i<a.length; i++) {
	    a[i] = ((Integer) heap.remove ()).intValue();
	}
	return a;
    }

    public static void main (String[] args) {

	int[] a = new int[10];
	for (int i = 0; i<a.length; i++) {
	    a[i] = randInt (0,100);
	}
	char c;
	if (args.length == 0 || args[0] == null || args[0].length() == 0) {
	    c = 's';
	} else {
	    c = args[0].charAt(0);	    
	}
	switch (c) {
	case 'm':
	    a = mergeSort (a);     break;
	case 'h':
	    a = heapSort (a);      break;
	default:
	    a = selectionSort (a); break;
	}
	for (int i = 0; i<a.length; i++) {
	    System.out.println (a[i]);
	}
    }
}