Sorting Algorithms in C# - Insertion Sort

We already have covered various sorting algorithms in C# that allow us to arrange the items in a collection in specific order using different strategies. The Bubble Sort compares adjacent elements and swaps them if their order is wrong. The Selection Sort shifts the minimum elements in a list to the left. Similarly, the Merge Sort and Quick Sort use the Divide and Conquer strategy to divide the collection into multiple sub-collections and arrange them in a particular order. The Insertion Sort is the last sorting algorithm we’ll cover in this tutorial.

The Insertion Sort algorithm is one of the simplest and easiest algorithms to understand and implement. Although it is not suitable for large data sets, it offers great real-world use cases. Let’s explore this algorithm and see how to implement it in C#.

What is Insertion Sort Algorithm?

The Insertion Sort algorithm compares the elements of a collection and sorts them sequentially. It starts with the second element in the collection, considering the first as sorted already. It compares an element to its preceding element and swaps it if it is lesser than that.

To understand this, let’s consider an array [5, 2, 7, 9, and 3]. The Insertion Sort starts at index 1 and compares it with the element at index 0. Here’s how the flow goes:
- Compare 2 and 5. 2<5. Swap. Array becomes [2, 5, 7, 9, 3].
- Compare 7 and 5. 7 > 5. No Swap. Array remains [2, 5, 7, 9, 3].
- Compare 9 and 7. 7 9 > 7. No Swap. Array remains [2, 5, 7, 9, 3].
- Compare 3 and 9. 3 < 9. Swap. Array becomes [2, 5, 7, 3, 9].
- Compare 3 and 7. 3 < 7. Swap. Array becomes [2, 5, 3, 7, 9].
- Compare 3 and 5. 3 < 5. Swap. Array becomes [2, 3, 5, 7, 9].
Our array is now sorted using the Insertion Sort.

Implementing Insertion Sort in C#

We already understand the working principle of the Insertion Sort. Now, it’s time to see its implementation in C#.

using System;
using System.Collections.Generic;
class Sorting {
    
static void InsertionSort(int[] numbers)
    {
        for (int i = 1; i < numbers.Length; i++) //Looping through the array
        {
            int current = numbers[i];  //Getting the current value at index 1
            int j = i-1;
            while (j >= 0 && numbers[j] > current) //if the current element is smaller than its preceding element
            {
                numbers[j + 1] = numbers[j];  //Swapping the elements
                j--;
            }

            numbers[j + 1] = current; //Getting the new current element
        }
    }
static void Main() {
    int[] nums = {2, 4, 1, 6, 5, 7};
    InsertionSort(nums);
    for(int i=0; i<nums.Length; i++)
    {
        Console.Write(nums[i] + " ");
    }
  }
}

When to Use the Insertion Sort Algorithm?

Although it is completely useless for large data sets, the Insertion Sort algorithm can be used in numerous scenarios, such as:

• Working with Smaller Data Sets: For datasets with around 10 to 20 elements, the Insertion Sort works better than the more complex algorithms since it does not require recursive calls and extra memory allocation.
• When Data is Nearly Sorted: The Insertion Sort algorithm can be an ideal choice for the datasets that are already sorted and do not require much rearrangement to be fully sorted.
• Where Sorting is Needed Continuously: The Insertion Sort algorithm can do the best job in online systems where data arrives incrementally and needs to be sorted continuously.
• Teaching Algorithm Fundamentals: When teaching data structures and algorithms to beginners, Insertion Sort can help you explain the concepts in simpler language with easy implementation.
• Where the Stable Sorting is Needed: The Insertion Sort algorithm maintains the relative positions of equal items in a collection while sorting. Therefore, in situations where stable sorting is a requirement, the Insertion Sort algorithm can be considered.

In our journey of sorting algorithms, we have covered almost all the basic sorting algorithms. I advise you to practice these algorithms more and more if you are taking this tutorial to land a C# developer job. Sorting algorithms comes in handy when solving numerous programming problems, and having good knowledge and hands-on practice with them can quickly lead you to a successful career. In the next article, we will start with the search algorithms used to look up an element in a collection rather than arrange it.