Insertion sort in C#

Insertion sort - overview

Insertion sort is a sorting algoritm with a simple implementation. It is pretty efficient when the array to be sorted contains a small number of elements. It is also efficient when the array is already almost sorted.

Description of the insertion sort algorithm

Insertion sort works in almost the same way as when a person wants to sort a hand of for example 5 playing cards.

First the left hand holds no cards and the 5 cards are lying face down on the table. Then we pick one card at a time from the table. To find the position of the card we compare it with the cards in the left hand, from the right to the left. Throughout the algorithm the cards in the left hand will always be sorted.

Insertion sort is an in-place algorithm

The sorting is performed in place. It means that the numbers are moved around within the array. Because of that it requires only a constant amount O(1) of memory space.

Computational complexity

The best case performance is when the input array is already sorted. In that case the algorithm only needs to do O(n) work.

For worst and average case the algorithm has a complexity of  O(n²).

Example of an implementation of insertion sort in C#

    private void SortArrayWithInsertionSort()
    {
        int[] array = { 7, 5, 17, 3, 1, 4, 4 };
        InsertionSort(array);

        // PrintResult(array);
    }

    private void InsertionSort(int[] array)
    {
        int j;
        int temp;

        for (int i = 1; i < array.Length; i++)
        {
            j = i;
            while (j > 0 && array[j] < array[j - 1])
            {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                j--;
            }
        }
    }