merge sort

gistfile1.cs

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