Sort.java

import java.util.Arrays;

public class Sort 
{
	/* 
		Selection is an in-place sort 
		Time: N^2
		The time it takes to sort is independent of how well sorted the array
		already is
	*/
	public static <T extends Comparable<T>> void selection(T[] arr) {
		int length = arr.length;

		// Loop through each position in array
		for (int pos = 0; pos < length; pos++) {

			// Initially make first element the smallest
			T minVal = arr[pos];
			int minIndex = pos;

			// Find the smallest
			for (int j = pos; j < length; j++) {

				if (arr[j].compareTo(minVal) < 0) {
					minVal = arr[j];
					minIndex = j;
				}
			}

			// Swap
			T temp = arr[pos];
			arr[pos] = minVal;
			arr[minIndex] = temp;
		}
	}

	/*
		Insertion sort
		Time: N^2
		Takes less time to sort if array is already partially sorted
	*/
	public static <T extends Comparable<T>> void insertion(T[] arr) {
		int length = arr.length;

		// We need to make an insertion for each element in the array
		for (int index = 1; index < length; index++) {
			
			T valToInsert = arr[index];
			int i = index - 1;
			
			// Determine where the element goes in the sorted part of array
			for (; i >= 0; i--) {

				if (arr[i].compareTo(valToInsert) <= 0) {
					arr[i + 1] = valToInsert;
					break;
				}

				// Shift to right
				arr[i + 1] = arr[i];
				arr[i] = valToInsert;
			}
		}
	}

	/*
		Shell sort -- based on insertion sort
		Time: Depends
	*/
	public static <T extends Comparable<T>> void shell(T[] arr) {
		int length = arr.length;

		// So let's try this with 3 first
		int h = 1;
		while (h < length/3)
			h = h*3 + 1;

		// Outer loop, changing value of h for sort
		while (h >= 1) {
			// i = index of value to insert
			for (int index = h; index < length; index++) {
				T valToInsert = arr[index];
				int i = index - h;

				// Determine where the element goes in the sorted part of array
				for (; i >= 0; i -= h) {

					if (arr[i].compareTo(valToInsert) <= 0) {
						arr[i + h] = valToInsert;
						break;
					}

					// Shift to right
					arr[i + h] = arr[i];
					arr[i] = valToInsert;
				}
			}
			h /= 3;
		}
	}

	/*
		Merge sort
	*/
	public static <T extends Comparable<T>> void merge(T[] arr) {
		//merge(arr, 0, arr.length);
		merge(arr, 0, arr.length-1);
	}

	private static <T extends Comparable<T>> void merge(T[] arr, int startIndex, int endIndex) {

		if (startIndex == endIndex)
			return;

		// Split
		int middle = (startIndex+endIndex)/2;
		int count = endIndex-startIndex+1;
		merge(arr, startIndex, middle);
		merge(arr, middle+1, endIndex);

		// Merge
		@SuppressWarnings("unchecked")
		T[] tempArr = (T[])new Comparable[count];
		int targetIndex = 0;
		int indexA = startIndex;
		int indexB = middle+1;
		while (indexA <= middle && indexB <= endIndex) {
			if (arr[indexA].compareTo(arr[indexB]) <= 0) {
				tempArr[targetIndex] = arr[indexA];
				indexA++;
			}
			else {
				tempArr[targetIndex] = arr[indexB];
				indexB++;
			}
			targetIndex++;
		}

		while (indexA <= middle) {
			tempArr[targetIndex] = arr[indexA];
			indexA++;
			targetIndex++;
		}

		while (indexB <= endIndex) {
			tempArr[targetIndex] = arr[indexB];
			indexB++;
			targetIndex++;
		}
		//System.out.println("Target index: " + targetIndex);
		//System.out.println(Arrays.toString(tempArr));

		int j = 0;
		for (int i = startIndex; i <= endIndex; i++) {
			arr[i] = tempArr[j];
			j++;
		}
	}

	/*
		Quick sort
		Average time: NlogN
		Worst time: N^2
	*/
	public static <T extends Comparable<T>> void quick(T[] arr) {
		quick(arr, 0, arr.length-1);
	}

	private static <T extends Comparable<T>> void quick(T[] arr, int startIndex, int endIndex) {

		if (startIndex >= endIndex)
			return;

		// Grab the first element as the partition value
		T partitionVal = arr[startIndex];
		int start = startIndex;
		int end = endIndex;

		while (end > start) {
			// Starting from the end, find a piece to swap
			while (end > start && arr[end].compareTo(partitionVal) >= 0)
				end--;
			arr[start] = arr[end];

			// Starting from the beginning, find a piece to go in that end spot
			while (end > start && arr[start].compareTo(partitionVal) <= 0)
				start++;
			arr[end] = arr[start];
		}

		// Assuming end == start
		arr[start] = partitionVal;

		// Quicksort each half
		quick(arr, startIndex, start - 1);
		quick(arr, start + 1, endIndex);
	}
}