Some common sorting algorithm snippet.

A.sorting_algorithm

Some common sorting algorithm snippet.

BinaryInsertion.java

/**
 * Insertion Sort class provides a static method for sorting an array using an
 * optimized binary insertion sort with half exchanges.
 * 
 * @author SylvanasSun
 *
 */
public class BinaryInsertion {

	// This class should not be instantiated.
	private BinaryInsertion() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 *
	 * @param a
	 *            the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		int length = a.length;
		for (int i = 1; i < length; i++) {
			// binary search to determine index j at which to insert a[i]
			Comparable v = a[i];
			int lo = 0, hi = i;
			while (lo < hi) {
				int mid = lo + (hi - lo) / 2;
				if (less(v, a[mid]))
					hi = mid;
				else
					lo = mid + 1;
			}

			// insertion sort with "half exchanges"
			// (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
			for (int j = i; j > lo; --j)
				a[j] = a[j - 1];
			a[lo] = v;
		}
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		int length = a.length;
		for (int i = 1; i < length; i++) {
			// binary search to determine index j at which to insert a[i]
			Object v = a[i];
			int lo = 0, hi = 1;
			while (lo < hi) {
				int mid = lo + (hi - lo) / 2;
				if (less(comparator, v, a[mid])) {
					hi = mid;
				} else {
					lo = mid + 1;
				}
			}

			// insertion sort with "half exchanges"
			// (insert a[i] at index j and shift a[j],...,a[i-1] to right)
			for (int j = i; j > lo; --j) {
				a[j] = a[j - 1];
			}
			a[lo] = v;
		}
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// test
	public static void main(String[] args) {
		String[] a = new Scanner(System.in).nextLine().split("\\s+");
		BinaryInsertion.sort(a);
		BinaryInsertion.print(a);
	}

}

Bubble.java

/**
 * Bubble Sort
 * 
 * @author SylvanasSun
 *
 */
public class Bubble {

	// This class should not be instantiated.
	private Bubble() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 * 
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 0; j < a.length - 1 - i; j++) {
				if (less(a[j + 1], a[j])) {
					exch(a, j, j + 1);
				}
			}
		}
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param a
	 *            a the arry to be sorted
	 * @param comparator
	 *            comparator the comparator specifying the order
	 */
	public static void sort(Object[] a, Comparator comparator) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 0; j < a.length - 1 - i; j++) {
				if (less(comparator, a[j + 1], a[j])) {
					exch(a, j, j + 1);
				}
			}
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// print array elements to console
	public static void print(Comparable[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// test
	public static void main(String[] args) {
		String[] s = new Scanner(System.in).nextLine().split("\\s+");
		Bubble.sort(s);
		Bubble.print(s);
	}
}

Insertion.java

/**
 * Insertion Sort
 * 
 * @author SylvanasSun
 *
 */
public class Insertion {

	// This class should not be instantiated
	private Insertion() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 * 
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		for (int i = 0; i < a.length; i++) {
			// a[i] insert to a[i-1]、a[i-2]、a[i-3]...
			for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
				exch(a, j, j - 1);
			}
		}
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = i; j > 0 && less(comparator, a[j], a[j - 1]); j--) {
				exch(a, j, j - 1);
			}
		}
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// test
	public static void main(String[] args) {
		String[] s = new Scanner(System.in).nextLine().split("\\s+");
		Insertion.sort(s);
		Insertion.print(s);
	}

}

InsertionX.java

/**
 * Insertion Sort. class provides static methods for sorting an array using an
 * optimized version of insertion sort (with half exchanges and a sentinel).
 * 
 * @author SylvanasSun
 *
 */
public class InsertionX {

	// This class should not be instantiated.
	private InsertionX() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 *
	 * @param a
	 *            the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		int length = a.length;

		// put smallest element in position to serve as sentinel
		int exchanges = 0;
		for (int i = length - 1; i > 0; i--) {
			if (less(a[i], a[i - 1])) {
				exch(a, i, i - 1);
				exchanges++;
			}
		}
		if (exchanges == 0)
			return;

		// insertion sort with half-exchanges
		for (int i = 2; i < length; i++) {
			Comparable v = a[i];
			int j = i;
			while (less(v, a[j - 1])) {
				a[j] = a[j - 1];
				j--;
			}
			a[j] = v;
		}
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		int length = a.length;

		// put smallest element in position to serve as sentinel
		int exchanges = 0;
		for (int i = length - 1; i > 0; i--) {
			if (less(comparator, a[i], a[i - 1])) {
				exch(a, i, i - 1);
				exchanges++;
			}
		}
		if (exchanges == 0)
			return;

		// insertion sort with half-exchanges
		for (int i = 2; i < length; i++) {
			Object v = a[i];
			int j = i;
			while (less(comparator, v, a[j - 1])) {
				a[j] = a[j - 1];
				j--;
			}
			a[j] = v;
		}
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// test
	public static void main(String[] args) {
		String[] a = new Scanner(System.in).nextLine().split("\\s+");
		InsertionX.sort(a);
		InsertionX.print(a);
	}

}

Merge.java

/**
 * Top-Down Merge Sort
 * 
 * @author SylvanasSun
 *
 */
public class Merge {

	// This class should not be instantiated.
	private Merge() {
	}

	// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
	private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
		// copy a[] to aux[]
		for (int k = lo; k <= hi; k++) {
			aux[k] = a[k];
		}

		// merge back to a[]
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				a[k] = aux[j++];
			} else if (j > hi) {
				a[k] = aux[i++];
			} else if (less(aux[j], aux[i])) {
				a[k] = aux[j++];
			} else {
				a[k] = aux[i++];
			}
		}
	}

	private static void merge(Object[] a, Object[] aux, Comparator comparator, int lo, int mid, int hi) {
		// copy a[] to aux[]
		for (int k = lo; k <= hi; k++) {
			aux[k] = a[k];
		}

		// merge back to a[]
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				a[k] = aux[j++];
			} else if (j > hi) {
				a[k] = aux[i++];
			} else if (less(comparator, aux[j], aux[i])) {
				a[k] = aux[j++];
			} else {
				a[k] = aux[i++];
			}
		}
	}

	// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
	private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
		if (hi <= lo)
			return;

		int mid = lo + (hi - lo) / 2;
		sort(a, aux, lo, mid);
		sort(a, aux, mid + 1, hi);
		merge(a, aux, lo, mid, hi);
	}

	private static void sort(Object[] a, Object[] aux, Comparator comparator, int lo, int hi) {
		if (hi <= lo)
			return;

		int mid = lo + (hi - lo) / 2;
		sort(a, aux, comparator, lo, mid);
		sort(a, aux, comparator, mid + 1, hi);
		merge(a, aux, comparator, lo, mid, hi);
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 * 
	 * @param a
	 *            the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		Comparable[] aux = new Comparable[a.length];
		sort(a, aux, 0, a.length - 1);
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		Object[] aux = new Object[a.length];
		sort(a, aux, comparator, 0, a.length - 1);
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// test
	public static void main(String[] args) {
		String[] a = new Scanner(System.in).nextLine().split("\\s+");
		Merge.sort(a);
		Merge.print(a);
	}

}

MergeBU.java

/**
 * Bottom-Up Merge Sort
 * 
 * @author SylvanasSun
 *
 */
public class MergeBU {

	// This class should not be instantiated.
	private MergeBU() {
	};

	// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
	private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
		// copy a[] to aux[]
		for (int k = lo; k <= hi; k++) {
			aux[k] = a[k];
		}

		// merge back to a[]
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				a[k] = aux[j++];
			} else if (j > hi) {
				a[k] = aux[i++];
			} else if (less(aux[j], aux[i])) {
				a[k] = aux[j++];
			} else {
				a[k] = aux[i++];
			}
		}
	}

	private static void merge(Object[] a, Object[] aux, Comparator comparator, int lo, int mid, int hi) {
		// copy a[] to aux[]
		for (int k = lo; k <= hi; k++) {
			aux[k] = a[k];
		}

		// merge back to a[]
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				a[k] = aux[j++];
			} else if (j > hi) {
				a[k] = aux[i++];
			} else if (less(comparator, aux[j], aux[i])) {
				a[k] = aux[j++];
			} else {
				a[k] = aux[i++];
			}
		}
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 * 
	 * @param a
	 *            the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		int N = a.length;
		Comparable[] aux = new Comparable[N];
		for (int len = 1; len < N; len *= 2) {
			for (int lo = 0; lo < N - len; lo += len + len) {
				int mid = lo + len - 1;
				int hi = Math.min(lo + len + len - 1, N - 1);
				merge(a, aux, lo, mid, hi);
			}
		}
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		int N = a.length;
		Object[] aux = new Object[N];
		for (int len = 1; len < N; len *= 2) {
			for (int lo = 0; lo < N - len; lo += len + len) {
				int mid = lo + len - 1;
				int hi = Math.min(lo + len + len - 1, N - 1);
				merge(a, aux, comparator, lo, mid, hi);
			}
		}
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// test
	public static void main(String[] args) {
		String[] a = new Scanner(System.in).nextLine().split("\\s+");
		MergeBU.sort(a);
		MergeBU.print(a);
	}

}

MergeX.java

/**
 * Merge Sort optimized using insertion handle small array.
 * 
 * @author SylvanasSun
 *
 */
public class MergeX {
	private static final int CUTOFF = 7; // cutoff to insertion sort

	// This class should not be instantiated.
	private MergeX() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 *
	 * @param a
	 *            the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		Comparable[] aux = a.clone();
		sort(aux, a, 0, a.length - 1);
	}

	/**
	 * Rearranges the array in ascending order, using the provided order.
	 *
	 * @param a
	 *            the array to be sorted
	 * @param comparator
	 *            the comparator that defines the total order
	 */
	public static void sort(Object[] a, Comparator comparator) {
		Object[] aux = a.clone();
		sort(aux, a, 0, a.length - 1, comparator);
	}

	private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				dst[k] = src[j++];
			} else if (j > hi) {
				dst[k] = src[i++];
			} else if (less(src[j], src[i])) {
				dst[k] = src[j++];
			} else {
				dst[k] = src[i++];
			}
		}
	}

	private static void merge(Object[] src, Object[] dst, Comparator comparator, int lo, int mid, int hi) {
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				dst[k] = src[j++];
			} else if (j > hi) {
				dst[k] = src[i++];
			} else if (less(comparator, src[j], src[i])) {
				dst[k] = src[j++];
			} else {
				dst[k] = src[i++];
			}
		}
	}

	private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
		// if (hi <= lo) return;
		if (hi <= lo + CUTOFF) {
			insertionSort(dst, lo, hi);
			return;
		}
		int mid = lo + (hi - lo) / 2;
		sort(dst, src, lo, mid);
		sort(dst, src, mid + 1, hi);

		// using System.arraycopy() is a bit faster than the above loop
		if (!less(src[mid + 1], src[mid])) {
			System.arraycopy(src, lo, dst, lo, hi - lo + 1);
			return;
		}

		merge(src, dst, lo, mid, hi);
	}

	private static void sort(Object[] src, Object[] dst, int lo, int hi, Comparator comparator) {
		if (hi <= lo + CUTOFF) {
			insertionSort(dst, lo, hi, comparator);
			return;
		}
		int mid = lo + (hi - lo) / 2;
		sort(dst, src, lo, mid, comparator);
		sort(dst, src, mid + 1, hi, comparator);

		// using System.arraycopy() is a bit faster than the above loop
		if (!less(comparator, src[mid + 1], src[mid])) {
			System.arraycopy(src, lo, dst, lo, hi - lo + 1);
			return;
		}

		merge(src, dst, comparator, lo, mid, hi);
	}

	// using insertion sort handle small array
	private static void insertionSort(Comparable[] a, int lo, int hi) {
		for (int i = lo; i <= hi; i++) {
			for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
				exch(a, j, j - 1);
			}
		}
	}

	private static void insertionSort(Object[] a, int lo, int hi, Comparator comparator) {
		for (int i = lo; i <= hi; i++) {
			for (int j = i; j > lo && less(comparator, a[j], a[j - 1]); j--) {
				exch(a, j, j - 1);
			}
		}
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// test
	public static void main(String[] args) {
		String[] a = new Scanner(System.in).nextLine().split("\\s+");
		MergeX.sort(a);
		MergeX.print(a);
	}

}

Quick.java

/**
 * Quick Sort
 * 
 * @author SylvanasSun
 *
 */
public class Quick {

	// This class should not be instantiated.
	private Quick() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 * 
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		shuffle(a);
		sort(a, 0, a.length - 1);
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		shuffle(a);
		sort(a, 0, a.length - 1, comparator);
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
	// and return the index j.
	private static int partition(Comparable[] a, int lo, int hi) {
		int i = lo; // left point
		int j = hi + 1; // right point
		Comparable v = a[lo]; // partition element

		while (true) {
			// scan left point
			while (less(a[++i], v)) {
				if (i == hi)
					break;
			}

			// scan right point
			while (less(v, a[--j])) {
				if (j == lo)
					break;
			}

			// check if point cross
			if (i >= j)
				break;

			exch(a, i, j);
		}

		// put partition element v to a[j]
		exch(a, lo, j);
		// now a[lo..j-1] <= a[j] <= a[j+1..hi]
		return j;
	}

	private static int partition(Object[] a, int lo, int hi, Comparator comparator) {
		int i = lo; // left point
		int j = hi + 1; // right point
		Object v = a[lo]; // partition element

		while (true) {
			// scan left point
			while (less(comparator, a[++i], v)) {
				if (i == hi)
					break;
			}

			// scan right point
			while (less(comparator, v, a[--j])) {
				if (j == lo)
					break;
			}

			// check if point cross
			if (i >= j)
				break;

			exch(a, i, j);
		}

		exch(a, lo, j);
		return j;
	}

	private static void sort(Comparable[] a, int lo, int hi) {
		if (hi <= lo)
			return;

		int j = partition(a, lo, hi);
		sort(a, lo, j - 1);
		sort(a, j + 1, hi);
	}

	private static void sort(Object[] a, int lo, int hi, Comparator comparator) {
		if (hi <= lo)
			return;

		int j = partition(a, lo, hi, comparator);
		sort(a, lo, j - 1, comparator);
		sort(a, j + 1, hi, comparator);
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// random sort an array
	private static void shuffle(Object[] a) {
		if (a == null)
			throw new IllegalArgumentException("array is null.");
		Random random = new Random();
		int N = a.length;
		for (int i = 0; i < N; i++) {
			int j = i + random.nextInt(N - i);
			Object temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}

	// test
	public static void main(String[] args) {
		String[] a = new Scanner(System.in).nextLine().split("\\s+");
		Quick.sort(a);
		Quick.print(a);
	}

}

Quick3way.java

/**
 * Quick Sort using three-way split
 * 
 * @author SylvanasSun
 *
 */
public class Quick3way {

	// This class should not be instantiated.
	private Quick3way() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 * 
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		shuffle(a);
		sort(a, 0, a.length - 1);
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		shuffle(a);
		sort(a, 0, a.length - 1, comparator);
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// quicksort the subarray a[lo .. hi] using 3-way partitioning
	private static void sort(Comparable[] a, int lo, int hi) {
		if (hi <= lo)
			return;

		int lt = lo, i = lo + 1, gt = hi;
		Comparable v = a[lo]; // partition element

		// a[lo..lt-1] < a[lt..gt] < a[gt+1..hi]
		while (i <= gt) {
			int cmp = a[i].compareTo(v);
			if (cmp < 0) {
				exch(a, i++, lt++);
			} else if (cmp > 0) {
				exch(a, i, gt--);
			} else {
				i++;
			}
		}
		sort(a, lo, lt - 1);
		sort(a, gt + 1, hi);
	}

	private static void sort(Object[] a, int lo, int hi, Comparator comparator) {
		if (hi <= lo)
			return;

		int lt = lo, i = lo + 1, gt = hi;
		Object v = a[lo]; // partition element

		// a[lo..lt-1] < a[lt..gt] < a[gt+1..hi]
		while (i <= gt) {
			int cmp = comparator.compare(a[i], v);
			if (cmp < 0) {
				exch(a, i++, lt++);
			} else if (cmp > 0) {
				exch(a, i, gt--);
			} else {
				i++;
			}
		}
		sort(a, lo, lt - 1, comparator);
		sort(a, gt + 1, hi, comparator);
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// random sort an array
	private static void shuffle(Object[] a) {
		if (a == null)
			throw new IllegalArgumentException("array is null.");
		Random random = new Random();
		int N = a.length;
		for (int i = 0; i < N; i++) {
			int j = i + random.nextInt(N - i);
			Object temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}

	public static void main(String[] args) {
		String[] a = new Scanner(System.in).nextLine().split("\\s+");
		Quick3way.sort(a);
		Quick3way.print(a);
	}

}

Selection.java

/**
 * Selection Sort
 * 
 * @author SylvanasSun
 *
 */
public class Selection {

	// This class should not be instantiated
	private Selection() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 * 
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		for (int i = 0; i < a.length; i++) {
			int min = i; // the smallest element index
			for (int j = i + 1; j < a.length; j++) {
				if (less(a[j], a[min]))
					min = j;
				exch(a, i, min);
			}
		}
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		for (int i = 0; i < a.length; i++) {
			int min = i;
			for (int j = i + 1; j < a.length; j++) {
				if (less(comparator, a[j], a[min]))
					min = j;
				exch(a, i, min);
			}
		}
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// test
	public static void main(String[] args) {
		String[] s = new Scanner(System.in).nextLine().split("\\s+");
		Selection.sort(s);
		Selection.print(s);
	}
}

Shell.java

/**
 * Shell Sort
 * 
 * @author SylvanasSun
 *
 */
public class Shell {

	// This class should not be instantiated.
	private Shell() {
	}

	/**
	 * Rearranges the array in ascending order, using the natural order.
	 *
	 * @param a
	 *            the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		int h = 1;
		while (h < a.length / 3) {
			// h sequence 1,4,13,40,121,364,1093,...
			h = h * 3 + 1;
		}
		while (h >= 1) {
			for (int i = h; i < a.length; i++) {
				// a[i] insert to a[i-h],a[i-2*h],a[i-3*h]...
				for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
					exch(a, j, j - h);
				}
			}
			h = h / 3;
		}
	}

	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param comparator
	 *            compare the comparator specifying the order
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparator comparator, Object[] a) {
		int h = 1;
		while (h < a.length / 3) {
			h = h * 3 + 1;
		}
		while (h >= 1) {
			for (int i = h; i < a.length; i++) {
				for (int j = i; j >= h && less(comparator, a[j], a[j - h]); j -= h) {
					exch(a, j, j - h);
				}
			}
			h = h / 3;
		}
	}

	/**
	 * Print array elements to console
	 * 
	 * @param a
	 *            a the array element print to console
	 */
	public static void print(Object[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}

	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}

	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// test
	public static void main(String[] args) {
		String[] a = new Scanner(System.in).nextLine().split("\\s+");
		Shell.sort(a);
		Shell.print(a);
	}

}