We have different sorting algorithms that we can use when we want to sort lists of elements. Insertion sort is one of the simplest algorithms that we can use to achieve our goal. In this article, we learn how insertion sort works, implement the algorithm in C#, and analyze its time and space complexity. 

To download the source code for this article, you can visit our GitHub repository.

Let’s start. 

Support Code Maze on Patreon to get rid of ads and get the best discounts on our products!
Become a patron at Patreon!

What is Insertion Sort?

As the name suggests, insertion sort is an algorithm that sorts a list of elements by taking each element and adding it to the correct position in the list. The algorithm iterates through the list until the array is sorted. 

To understand how insertion sort works, let’s use the analogy of a card player who wants to sort some playing cards.

The player starts with an empty left hand with all the cards on the table. The empty hand in this case symbolizes an empty array that stores the sorted values.

Then, the player takes one card at a time and places it in the correct position in the left hand. When finding the correct position to place the new card, the player compares the card with the sorted ones in the hand from right to left. 

Let’s take a deep dive and have and learn how insertion sort works. 

How Does Insertion Sort Algorithm Work?

To illustrate how the insertion sort algorithm works, let’s assume we intend to sort this array:

int[] array = { 86, 13, 60, 46, 73, 52 };

Assuming 86 is a sorted list of the first item, we are going to compare 86 with 13. Since 13 is less than 86, we switch their positions and the array becomes:

13, 86, 60, 46, 73, 52

86 is greater than 60 so we switch their positions and the array becomes:

13, 60, 86, 46, 73, 52

86 is greater than 46, hence we shift 86 to the right:

13, 60, 46, 86, 73, 52

60 is greater than 46 while 46 is less than 13, so we shift 60 to the right: 

13, 46, 60, 86, 73, 52

86 is greater than 73 and 73 is greater than 60, so we are going to shift 86 to the right:

13, 46, 60, 73, 86, 52

86 is greater than 52 so we shift it to the right:

13, 46, 60, 73, 52, 86

73 is greater than 52 so we shift it to the right:

13, 46, 60, 52, 73, 86

52 is less than 60 while it’s greater than 46, hence we switch 52 and 60 to complete the sorting process: 

13, 46, 52, 60, 73, 86

In summary, we can see that insertion sort uses this working principle:

  1. First, compare the current element with its adjacent element.
  2. In case we find a position in the ordered array where we can insert the current element, we create space by shifting the elements to right and inserting the current element at the correct position.
  3. Repeat steps 1 and 2 until the last element in the unsorted array is placed in its correct position.

How to Implement Insertion Sort in C#?

We can implement the insertion sort algorithm recursively or through an imperative approach. 

Let’s start with the imperative approach.

Imperative Implementation

We are going to define a method SortArray() as our entry point into the sorting algorithm. The method takes int[] array and int length as inputs:

public int[] SortArray(int[] array, int length)
{
    for (int i = 1; i < length; i++)
    {
        var key = array[i];
        var flag = 0;

        for (int j = i - 1; j >= 0 && flag != 1;)
        {
            if (key < array[j])
            {
                array[j + 1] = array[j];
                j--;
                array[j + 1] = key;
            }
            else flag = 1;
        }
    }

    return array;
}

SortArray() uses two nested loops to sort the array elements. We can see that the iteration process starts from the second element i = 1.

We have to assume that the array is logically divided into two segments with the left segment holding sorted elements while the right segment holding unsorted array elements. 

For each pass of the outer loop, the current element key = array[i] is inserted into its correct position in the array. The inner loop checks if the current element is less than, which is the last element in the sorted segment of the array. If key < array[j] is true, we shift their positions, otherwise, we set the flag variable to 1 to allow the outer loop to iterate:

for (int j = i - 1; j >= 0 && flag != 1;)
{
    if (key < array[j])
    {
        array[j + 1] = array[j];
        j--;
        array[j + 1] = key;
    }
    else flag = 1;
}

This process is done iteratively until the array is sorted. 

Finally, we can verify that the SortArray() method sorts a given unsorted array accurately:

var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new InsertionSortMethods();

var sortedArray = sortFunction.SortArray(array, array.Length);

Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(sortedArray, expected);

Recursive Implementation

We are going to define a method SortArrayRecursive() that takes array and length as inputs:

public int[] SortArrayRecursive(int[] array, int length) 
{
    if (length <= 1)
    {
        return array;
    }

    SortArrayRecursive(array, length - 1);
    var key = array[length - 1];
    var k = length - 2;

    while (k >= 0 && array[k] > key)
    {
        array[k + 1] = array[k];
        k = k - 1;
    }

    array[k + 1] = key;

    return array;
}

We start by checking whether we are attempting to sort an array that contains a single element as our base case here: 

if (length <= 1)
{
    return array;
}

If the base-case scenario is not true, SortArrayRecursive() calls itself while passing the array and length -1 as its parameters. 

To hold the value of the last element in the sorted subarray ( array[length - 1]), we assign it to key . k holds the second last element of the array, which we are going to compare against key. 

Next, we are going to iterate through the array while comparing k it with key . We shift their positions if k are greater than key: 

while (k >= 0 && array[k] > key)
{
    array[k + 1] = array[k];
    k = k - 1;
}

Finally, we can verify that the SortArrayRecursive() method sorts a given unsorted array accurately:

var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new InsertionSortMethods();

var sortedArray = sortFunction.SortArrayRecursive(array, array.Length);

Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(sortedArray, expected);

Space and Time Complexity of Insertion Sort Algorithm

As we’ve seen in the implementation section, the insertion sort algorithm sorts all the elements in place. Therefore, the space complexity of insertion sort is O(1). 

Best-Case Time Complexity

Insertion sort encounters the best-case time complexity scenario when we attempt to sort an array that is already sorted. In this case, the algorithm is going to compare each array element to its predecessor. Assuming the size of the array is N, the algorithm will take N steps to sort the array. 

Therefore, the best-case time complexity of insertion sort is O(N). 

Average-Case Time Complexity

When insertion sort encounters random array elements it encounters an average-case time complexity scenario. The algorithm compares each array element to its predecessor and finding the correct position to place elements would take O(N2). 

Worst-Case Time Complexity

This scenario occurs when insertion sort encounters a reversed list. The algorithm inserts every array element at the beginning of the sorted subarray, which makes it have a time complexity of  O(N2).

Advantages of Insertion Sort Algorithm

To start with, it is simple to learn and use, which makes it easy to implement. 

Besides being simple to implement, insertion sort is effective when used in memory-intensive applications as it does not require a lot of additional memory. 

Insertion sort maintains the relative order of the array elements in case it encounters two similar values (stable), unlike quicksort, which is unstable. 

Disadvantages of Insertion Sort Algorithm

We have learned that insertion sort has an average-case and worst-case complexity of O(N2). This makes the algorithm less efficient when compared to algorithms such as quicksort and merge sort. 

Performance Tests

Let’s assess how insertion sort performs by measuring the time it takes for it to sort an array. For these tests, we are going to measure both the imperative and recursive implementations of the insertion sort algorithm.  

First, let’s write a method to generate a set of random array elements:

public static int[] CreateRandomArray(int size)
{
    var array = new int[size];
    var rand = new Random();

    for (int i = 0; i < size; i++)
        array[i] = rand.Next();

    return array;
}

The CreateRandomArray() the method takes an integer as its sole input. Using the inbuilt Random class, we generate integer values that we’re going to put into the array.

Next, we are going to define a method that generates a sequence of elements. This method simulates a scenario where we have a sorted array:

public static int[] CreateSortedArray(int size)
{
    var array = new int[size];

    for (int i = 0; i < size; i++)
        array[i] = i;

    return array;
}

To make the tests as realistic as possible, we are going to use the inbuilt class Array.Reverse() to reverse the arrays generated from the CreateSortedArray() method. 

We can create a simple method CreateReversedArray() that takes an int[] array as its sole parameter and returns a reversed array:

public static int[] CreateReversedArray(int[] array)
{
    Array.Reverse(array);

    return array;
}

Next, we are going to create an object that holds different arrays that have random and sorted values:

public IEnumerable<object[]> SampleArrays()
{
    yield return new object[] { CreateRandomArray(200), 200, "Small Unsorted" };
    yield return new object[] { CreateRandomArray(2000), 2000, "Medium Unsorted" };
    yield return new object[] { CreateRandomArray(20000), 20000, "Large Unsorted" };
    yield return new object[] { CreateSortedArray(200), 200, "Small Sorted" };
    yield return new object[] { CreateSortedArray(2000), 2000, "Medium Sorted" };
    yield return new object[] { CreateSortedArray(20000), 20000, "Large Sorted" };
    yield return new object[] { CreateReversedArray(CreateSortedArray(200)), 200, "Small Reversed" };
    yield return new object[] { CreateReversedArray(CreateSortedArray(2000)), 2000, "Medium Reversed" };
    yield return new object[] { CreateReversedArray(CreateSortedArray(20000)), 20000, "Large Reversed" };
}

Each object entry has three values: an integer array e.g.  CreateRandomArray(200), its length (200), and a string object storing the name of that array (“Small Unsorted”). 

The array objects have different sizes (to simulate time complexity scenarios) and hold random numbers that are added by the CreateRandomArray() method.

The CreateSortedArray() the method creates arrays that have values that are sorted. On the other hand, CreateReversedArray()creates reverses a sorted array to simulate worst-case complexity scenarios. 

Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:

|             Method |        array | length |       arrayName |         Mean |       Error |       StdDev |
|------------------- |------------- |------- |---------------- |-------------:|------------:|-------------:|
|          SortArray |   Int32[200] |    200 |  Small Reversed |     403.4 ns |     7.89 ns |      9.39 ns |
| SortArrayRecursive |   Int32[200] |    200 |  Small Reversed |   1,055.7 ns |    21.12 ns |     41.69 ns |
|          SortArray |   Int32[200] |    200 |    Small Sorted |     400.2 ns |     7.72 ns |      6.84 ns |
| SortArrayRecursive |   Int32[200] |    200 |    Small Sorted |   1,022.0 ns |    18.79 ns |     15.69 ns |
|          SortArray |   Int32[200] |    200 |  Small Unsorted |     398.9 ns |     7.62 ns |      5.95 ns |
| SortArrayRecursive |   Int32[200] |    200 |  Small Unsorted |   1,031.8 ns |    19.95 ns |     24.50 ns |
|          SortArray |  Int32[2000] |   2000 | Medium Reversed |   3,849.0 ns |    76.73 ns |     88.36 ns |
| SortArrayRecursive |  Int32[2000] |   2000 | Medium Reversed |  12,186.8 ns |   240.80 ns |    395.64 ns |
|          SortArray |  Int32[2000] |   2000 |   Medium Sorted |   3,850.5 ns |    73.60 ns |     78.75 ns |
| SortArrayRecursive |  Int32[2000] |   2000 |   Medium Sorted |  12,077.7 ns |   240.66 ns |    286.49 ns |
|          SortArray |  Int32[2000] |   2000 | Medium Unsorted |   3,958.1 ns |    77.61 ns |    211.15 ns |
| SortArrayRecursive |  Int32[2000] |   2000 | Medium Unsorted |  13,002.4 ns |   577.56 ns |  1,666.39 ns |
|          SortArray | Int32[20000] |  20000 |  Large Reversed |  59,549.5 ns | 4,488.07 ns | 13,020.71 ns |
| SortArrayRecursive | Int32[20000] |  20000 |  Large Reversed | 160,805.7 ns | 3,094.82 ns |  3,800.72 ns |
|          SortArray | Int32[20000] |  20000 |    Large Sorted |  36,877.7 ns |   681.48 ns |    669.31 ns |
| SortArrayRecursive | Int32[20000] |  20000 |    Large Sorted | 156,821.2 ns | 2,280.12 ns |  1,780.17 ns |
|          SortArray | Int32[20000] |  20000 |  Large Unsorted |  36,467.7 ns |   483.45 ns |    452.22 ns |
| SortArrayRecursive | Int32[20000] |  20000 |  Large Unsorted | 158,289.3 ns | 2,164.03 ns |  1,807.06 ns |

SortArrayRecursive() is at least two times slower than the imperative implementation SortArray() in all cases. For example, when sorting a small reversed array, SortArrayRecursive() takes approximately 1,056 ns while SortArray() takes about 404 ns.

The recursive implementation of the insertion sort algorithm is slower than its imperative implementation in C# as it requires the allocation of a new stack frame every time SortArrayRecursive() calls itself.  

From the benchmark, we can also see that the algorithm takes longer to sort reversed arrays, which simulates the algorithm’s worst-case complexity. Let’s analyze the results obtained from sorting the largest array consisting of 20,000 elements. SortArray() takes almost twice as long to sort a reversed array (59,549.5 ns) as compared to sorting a randomized array (36,467.7 ns).

Conclusion

In this article, we have learned how insertion sort in C# works. It is simple to implement and use but it is not efficient. 

Liked it? Take a second to support Code Maze on Patreon and get the ad free reading experience!
Become a patron at Patreon!