merge sort

gistfile1.java

/**
 * Method sorts a list ascendingly using merge sort algorithm.
 * 
 * @param <T>
 *            Non null class, that implements comparable interface.
 * @param data
 *            List of T type elements, to be sorted ascendingly.
 * @throws java.lang.NullPointerException
 *             If any element in the list is 'null'.
 * @throws java.lang.UnsupportedOperationException
 *             If list is unmodifiable or immutable.
 */
public static <T extends Comparable<? super T>> //
void mergeSort(final List<T> data) {
	mergeSort(data, 0, data.size() - 1);
}

/**
 * Method sorts a part of list ascendingly using merge sort algorithm.
 * 
 * @param <T>
 *            Non null class, that implements comparable interface.
 * @param data
 *            List of T type elements, to be sorted ascendingly.
 * @throws java.lang.NullPointerException
 *             If any element in the list is 'null'.
 * @throws java.lang.UnsupportedOperationException
 *             If list is unmodifiable or immutable.
 */
public static <T extends Comparable<? super T>> //
void mergeSort(final List<T> data, int lowBound, int highBound) {
	if (lowBound >= highBound)
		return;

	// partition
	int maxLowBound = (lowBound + highBound) / 2;
	int minHighBound = maxLowBound + 1;
	
	mergeSort(data, lowBound, maxLowBound);
	mergeSort(data, minHighBound, highBound);

	// merge
	boolean comp;
	Queue<T> storageLow = new LinkedList<T>();
	Queue<T> storageHigh = new LinkedList<T>();
	
	for (int i = lowBound; i <= maxLowBound; i++)
		storageLow.add(data.get(i));
	for (int i = minHighBound; i <= highBound; i++)
		storageHigh.add(data.get(i));

	while ((storageLow.size() > 0) && ((storageHigh.size() > 0))) {
		comp = storageLow.peek().compareTo(storageHigh.peek()) < 0;
		data.set(lowBound++, comp ? storageLow.poll() : storageHigh.poll());
	}

	while (storageLow.size() > 0)
		data.set(lowBound++, storageLow.poll());
	while (storageHigh.size() > 0)
		data.set(lowBound++, storageHigh.poll());
}