Insertion Sort – Data Structures and Algorithms using C#

Insertion sort is not the best sorting algorithm in terms of performance, but its a little more efficient than selection sort and bubble sort in practical scenarios.

How Insertion Sort Works ?

let’s say we have a set of event registered form filled by subscribers in our hand and we want to arrange these forms in increasing order of registration numbers. One of the things that we can do is initially we can keep all the cards in our left hand and take one form and put it on the desk, this will be your sorted list. The rest of the forms will be in your hand. After this you take another form and compare it with already sorted list and place it in the right order. We will keep on repeating the process until there are no more papers in your hand. This is the algorithm behind insertion sort.

C# Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 5, 12, 4, 32, 67, 23, 9, 14, 99, 21};
 
            // call the function InsertionSort
            InsertionSort(arr);
 
            // print the sorted array
            Console.WriteLine("Sorted Array: ");
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + " ");
            }
 
            Console.ReadKey();
        }
 
        static void InsertionSort(int[] arr)
        {
            for (int i = 0; i < arr.Length - 1; i++) { for (int j = i + 1; j > 0; j--)
                {
                    if (arr[j - 1] > arr[j])
                    {
                        int temp = arr[j - 1];
                        arr[j - 1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
 
        }
    }
Complexity of Insertion Sort

The worst case for insertion sort will occur when the input list is in decreasing order. To insert the last element, we need at most  (n-1) comparisons and at most (n – 1)  swaps. To insert the second to last element, we need at most  (n – 2) comparisons and at most  (n – 2)swaps, and so on. Therefore, The number of operations needed to perform insertion sort is:

2 x ( 1 + 2 + …. + (n – 2) + (n – 1)) = n(n – 1)

i.e O(n^2)

Hence, we can say that the bubble sort runs in O(n^2) time in its worst and average cases..

Insertion sort runs in O(n) time in its best case.

Insertion sort is a stable sort with a space complexity of O(1).

 
So, it was all about Insertion Sorting Algorithm, if you have any query then please comment below and let us know. If you liked this article, then please follow us on Facebook to get notification for new posts.

Happy Learning 🙂

Rahul is a Data Geek, technology enthusiast, a passionate writer, thinker with passion for computer programming.  He loves to explore technology and finds ultimate joy when writing about trending technology, geek stuff and web development.