SlowSort.java

import java.util.Comparator;
import java.util.List;

public class SlowSort {

	public static <T extends Comparable<? super T>> void slowSort(T[] array) {
		slowSort(array, 0, array.length);
	}
	
	public static <T> void slowSort(T[] array, Comparator<? super T> comparator) {
		slowSort(array, 0, array.length, comparator);
	}
	
	public static <T extends Comparable<? super T>> void slowSort(List<T> list) {
		final int siz = list.size();
		@SuppressWarnings("unchecked")
		T[] a = (T[]) list.toArray(new Comparable[siz]);
		slowSort(a, 0, siz);
		for (int i = 0; i < siz; i++) {
			list.set(i, a[i]);
		}
	}
	
	public static <T> void slowSort(List<T> list, Comparator<? super T> comparator) {
		final int siz = list.size();
		@SuppressWarnings("unchecked")
		T[] a = (T[]) list.toArray(new Object[siz]);
		slowSort(a, 0, siz, comparator);
		for (int i = 0; i < siz; i++) {
			list.set(i, a[i]);
		}
	}

	private static <T> void slowSort(T[] a, int i, int j, Comparator<? super T> c) {
		/* Slow-sorts the subarray a[i] ... a[j-1] with the following procedure:
		 * 
		 * 1) Find the maximum of the sublist, and swap it into the last position.
		 * 2) slowSort the rest of the array.
		 * 
		 * Step 1 can be further decomposed as follows:
		 * 
		 * 1.1) Let n = j - i.  Find the maximum of the first n / 2 elements by slowSort.
		 * 1.2) Find the maximum of the rest of the elements by slowSort.
		 * 1.3) Return the maximum of the two maxima.
		 */
		
		final int n = j - i;
		if (n <= 1) return;
		
		/* Step 1. */
		int k = i + n / 2;
		slowSort(a, i, k, c);
		slowSort(a, k, j, c);
		if (c.compare(a[--k], a[--j]) > 0) {
			T tmp = a[j];
			a[j] = a[k];
			a[k] = tmp;
		}
		
		/* Step 2. */
		slowSort(a, i, j, c);
	}
	
	private static <T extends Comparable<? super T>> void slowSort(T[] a, int i, int j) {	
		/* Slow-sorts the subarray a[i] ... a[j-1] with the following procedure:
		 * 
		 * 1) Find the maximum of the sublist, and swap it into the last position.
		 * 2) slowSort the rest of the array.
		 * 
		 * Step 1 can be further decomposed as follows:
		 * 
		 * 1.1) Let n = j - i.  Find the maximum of the first n / 2 elements by slowSort.
		 * 1.2) Find the maximum of the rest of the elements by slowSort.
		 * 1.3) Return the maximum of the two maxima.
		 */
		
		final int n = j - i;
		if (n <= 1) return;
		
		/* Step 1. */
		int k = i + n / 2;
		slowSort(a, i, k);
		slowSort(a, k, j);
		if (a[--k].compareTo(a[--j]) > 0) {
			T tmp = a[j];
			a[j] = a[k];
			a[k] = tmp;
		}
		
		/* Step 2. */
		slowSort(a, i, j);
	}
}