Insertion sort is just another algorithm with which we can sort single dimensional arrays. Similarly to selection sort, it is also one of the simplest algorithms to sort objects in accending or decending order. Therefore, it also doesn’t score any higher in efficiency.

We begin the same way as with selection sort by dividing into 2 parts, namely sorted and unsorted. However, with insertion sort, we need to leave the first object of the array in the sorted part of the array. Furthermore, it’s going to serve as a reference point when we start with our first iteration.

With each iteration, the algorithm picks the first element in the unsorted part of the array and inserts it in a suitable position in the sorted part. In order to sort the entire array, we iterate this operation as many times until the unsorted part is empty.

Insertion sort in C#

Let’s first take a look at the code to get a better understanding of how it actually works.

public static class InsertionSort
    {
        public static void Sort<T>(T[] array) where T : IComparable
        {
            for (int i = 1; i < array.Length; i++)
            {
                int j = i;
                while (j > 0 && array[j].CompareTo(array[j - 1]) < 0)
                {
                    Swap(array, j, j - 1);
                    j--;
                }
            }
        }

        private static void Swap<T>(T[] array, int first, int second)
        {
            T temp = array[first];
            array[first] = array[second];
            array[second] = temp;
        }
    }

First of all, we create a static class for the insertion sort, which contains 2 methods. Swap method is a private method, which we use only inside the class. The sort method is where all the work gets done. Furthermore, it accepts 1 parameter, which is the array we want to sort.

The Sort method also accepts arrays of different data type, which makes it convenient for reuse. In detail, we accomplished this by using the IComparable interface and its method CompareTo.

As you can see, we start by creating a for loop to iterate through the whole array. The variable i is set to 1, because we will skip the first element, since it already belongs to the sorted part.

Next, we nest a while loop inside, which will loop through the entire sorted part and find the correct place for an object. In other words, for loop loops forward, while while loop propagates backwards.

Conclusion

Thank you for visiting this post about implementation of insertion sort in C# and I hope you found it useful.

You can also download the demo project and try it out yourself.