Class InsertionSort

An IInputMutatingSort implementation based on insertion sort.

Inheritance
System.Object
InsertionSort
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Lists.Sorting
Assembly: MoreStructures.dll
Syntax
public class InsertionSort : IInputMutatingSort
Remarks

ALGORITHM
- This sorting algorithm split the list L being sorted in two parts: the sorted part, located at the beginning of the list (L[..i]), and the unsorted part, located at the end of the list (L[i..]).
- At the beginning the sorted part is empty (i.e. length 0) and the unsorted part covers the entire list (i.e. length n).
- The algorithm runs n - 1 1-based iterations, where n is the number of items in the list.
- At the beginning of iteration i, the sorted sub-list is L[..i] and the unsorted sub-list is L[i..].
- The first item L[i], of the unsorted sub-list L[i..], is compared against its predecessor, L[i - 1].
- If L[i] is smaller than L[i - 1], the two items are swapped and the new L[i - 1] is compared with L[i - 2]. Comparisons and swapping continues until the predecessor is not bigger than its successor, potentially until the head of the list is reached.
- When a L[j] is found, which is not strictly smaller than L[j - 1], L[.. (i + 1)] is sorted, and the iteration i can terminate.

COMPLEXITY
- Each of the n - 1 iterations runs at most i - 1 comparisons, if it has to swap all the way up to the head of the list.
- The total number of comparisons, over the n iterations, is around n * n / 2.
- Therefore, Time Complexity is O(n^2) and Space Complexity is O(1), since the algorithm runs in place and hence only requires additional constant space to perform the sorting.

Methods

| Improve this Doc View Source

Sort<T>(IList<T>)


Uses the insertion sort algorithm with the default comparer for T, given by .

Declaration
public void Sort<T>(IList<T> list)
    where T : IComparable<T>
Parameters
Type Name Description
IList<T> list
Type Parameters
Name Description
T
Remarks

| Improve this Doc View Source

Sort<T>(IList<T>, IComparer<T>)


Uses the insertion sort algorithm with the specified comparer.

Declaration
public void Sort<T>(IList<T> list, IComparer<T> comparer)
Parameters
Type Name Description
IList<T> list
IComparer<T> comparer
Type Parameters
Name Description
T
Remarks

Implements

Extension Methods