Merge sort

Will take O(n * log (n)) time, and does not depend on input.

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());
	}

view raw gistfile1.java hosted with ❤ by GitHub

C#

	/// <summary>
	/// Method sorts a list ascendingly using merge sort algorithm.
	/// </summary>
	/// <typeparam name="T"> Non null class, that implements comparable interface.
	/// </typeparam>
	/// <param name="data">List of T type elements, to be sorted ascendingly.</param>
	/// <exception cref="System.NullReferenceException">
	/// If any element in the list is 'null'. (Other then first one)
	/// </exception>
	/// <exception cref="System.NotSupportedException">
	/// If list is readonly.
	/// </exception>
	public static void mergeSort<T>(IList<T> data) where T : IComparable<T>
	{
	mergeSort(data, 0, data.Count - 1);
	}
	/// <summary>
	/// Method sorts a part of list ascendingly using merge sort algorithm.
	/// </summary>
	/// <typeparam name="T"> Non null class, that implements comparable interface.
	/// </typeparam>
	/// <param name="data">List of T type elements, to be sorted ascendingly.</param>
	/// <exception cref="System.NullReferenceException">
	/// If any element in the list is 'null'. (Other then first one)
	/// </exception>
	/// <exception cref="System.NotSupportedException">
	/// If list is readonly.
	/// </exception>
	public static void mergeSort<T>(IList<T> data, int lowBound, int highBound)
	where T : IComparable<T>
	{
	if (lowBound >= highBound)
	return;
	// partition
	int maxLowBound = (lowBound + highBound) / 2;
	int minHighBound = maxLowBound + 1;
	mergeSort(data, lowBound, maxLowBound);
	mergeSort(data, minHighBound, highBound);
	// merge
	bool comp;
	Queue<T> storageLow = new Queue<T>();
	Queue<T> storageHigh = new Queue<T>();
	for (int i = lowBound; i <= maxLowBound; i++)
	storageLow.Enqueue(data[i]);
	for (int i = minHighBound; i <= highBound; i++)
	storageHigh.Enqueue(data[i]);
	while ((storageLow.Count() > 0) && ((storageHigh.Count() > 0)))
	{
	comp = storageLow.Peek().CompareTo(storageHigh.Peek()) < 0;
	data[lowBound++] = comp ? storageLow.Dequeue() : storageHigh.Dequeue();
	}
	while (storageLow.Count() > 0)
	data[lowBound++] = storageLow.Dequeue();
	while (storageHigh.Count() > 0)
	data[lowBound++] = storageHigh.Dequeue();
	}

view raw gistfile1.cs hosted with ❤ by GitHub