Insertion sort

Efficient for small lists, with size less then 30.

Special cases are:

• if list is almost sorted, it will be near linear time
• if sorted list is reversed, it will be quadratic time

Java

	/**
	* Method sorts a list ascendingly using insertion 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 insertionSort(final List<T> data)
	throws java.lang.NullPointerException,
	java.lang.UnsupportedOperationException {
	int i, j;
	for (i = 1; i < data.size(); i++) {
	T temp = data.get(i);
	j = i;
	while ((j > 0) && (temp.compareTo(data.get(j - 1)) < 0)) {
	data.set(j, data.get(j - 1));
	j--;
	}
	data.set(j, temp);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

C#

	/// <summary>
	/// Method sorts a list ascendingly using insertion 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 insertionSort<T>(IList<T> data) where T : IComparable<T>
	{
	int i, j;
	for (i = 1; i < data.Count; i++)
	{
	T temp = data[i];
	j = i;
	while ((j > 0) && (temp.CompareTo(data[j - 1]) < 0))
	{
	data[j] = data[j - 1];
	j--;
	}
	data[j] = temp;
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub