Updated on
Insertion sort is a sorting algorithm that keeps a sorted part at the start of the array and inserts each next element into its place there, shifting the bigger ones one position to the right. We can write it in C# with two nested loops or with one recursive method, and neither needs a second array.
We have different sorting algorithms that we can use when we want to sort lists of elements, and insertion sort is one of the simplest. We’ll see how it works, implement it in C# both ways, analyze its time and space complexity, and measure both versions.
Let’s start.Â
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 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 greater 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
Every pass grows the sorted part on the left by one element, so our six elements need five passes.

Insertion sort on our six-element array: after each pass, one more element belongs to the sorted part on the left.
In summary, we can see that insertion sort uses this working principle:
- First, compare the current element with its adjacent element.
- 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.
- 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#?
To implement insertion sort in C#, we loop over the array from the second element and insert each element into the sorted part on its left.
The outer loop picks the element at index i and keeps it in a key variable. The inner loop walks left through the sorted part. Every element bigger than key moves one position to the right, and key takes the slot it leaves. When the inner loop meets an element that is not bigger, key is in place and the outer loop moves on.
After the pass for index i, the first i + 1 elements are sorted. When the outer loop reaches the end, the whole array is.
The comparison is a strict <, so equal values never pass each other and the sort is stable. Everything happens inside the array we pass in, so the method sorts in place and returns the same instance.
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() in an InsertionSortMethods class of a new console app 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 compares the current element with array[j], starting from the last element of the sorted segment. If key < array[j] is true, we move array[j] one position to the right and write key into the slot it leaves. Otherwise, we set the flag variable to 1, which ends the inner loop and lets the outer loop move on to the next element:
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, in a test method of an MSTest project that references our app, 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(expected, sortedArray);
Recursive Implementation
We are going to define a method SortArrayRecursive() in the same class 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.Â
When the recursive call returns, the first length - 1 elements are sorted. The element right after them, array[length - 1], is the one we insert, so we keep it in key. k starts at length - 2, the index of the last sorted element.
Next, we walk left from k and compare array[k] with key. Every element greater than key moves one position to the right:
while (k >= 0 && array[k] > key)
{
array[k + 1] = array[k];
k = k - 1;
}
When the loop stops, k + 1 is the free slot, and array[k + 1] = key puts the element there. Unlike the imperative version, we write key only once per element.
The recursion has a limit, though. Each call waits for the call on a one element shorter array, so the recursion goes as deep as the array is long. When we tried it on Windows with .NET 10, an array of 12,000 elements sorted fine, and 13,000 elements crashed the process with a stack overflow. The exact number depends on the stack size the process gets and on how the JIT compiles the method: with tiered compilation switched off, the same 13,000 elements sorted fine. The imperative version has no such limit, so that’s the one to use for real data.
Finally, in a second test method, 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(expected, sortedArray);
What Is the Time and Space Complexity of Insertion Sort?
Insertion sort runs in O(N) time in the best case and O(N²) in the average and the worst case. The imperative version needs O(1) extra space.
The best case is an array that is already sorted. Each new element is compared once with its left neighbour and stays where it is, so 2,000 sorted elements take 1,999 comparisons.
On random data, each element moves past about half of the sorted part, which gives roughly N²/4 comparisons. For 2,000 random elements we counted about a million. A reversed array is the worst case: every element travels all the way to the front, and the count reaches N(N − 1)/2, which is 1,999,000.
Both of our versions sort in place and are stable. The recursive one also needs O(N) space on the call stack, one call per element.
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 makes N − 1 comparisons and moves nothing.Â
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. On average, each element moves past half of the sorted part before it finds its position, which takes 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, the imperative version is effective when used in memory-intensive applications as it does not require any 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.Â
Insertion sort is also quick on small arrays and on arrays that are almost sorted, because there each element moves only a few positions. It reaches its O(N) best case with no extra code, while bubble sort needs an early-exit flag for it, and selection sort makes the same N(N − 1)/2 comparisons whatever order the input is in. That is why .NET’s Array.Sort() switches to insertion sort for short partitions, as our quicksort article explains. A comment in the .NET runtime’s Array.cs source says of that cut-off of 16 elements: “Empirically, 16 seems to speed up most cases without slowing down others, at least for integers.”
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 with BenchmarkDotNet. 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 in our InsertionSortMethods class 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() method takes an integer as its sole input. Using the built-in Random class, we generate random numbers that we’re going to put into the array.
Next, we are going to define a method in the same class 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 simulate the worst case, we are going to use the built-in Array.Reverse() method to reverse the arrays generated from the CreateSortedArray() method.Â
We can create a simple method CreateReversedArray() in the same class 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;
}
Benchmarking an in-place sort has a catch. Both of our methods rearrange the array we pass in, and BenchmarkDotNet runs each method many times over. With one shared array, only the first call would get random or reversed numbers, and every other call would get the sorted result of the call before it.
That is exactly what happened in the first version of this article: every row of its table grew about ten to fifteen times for ten times more elements, which is the O(N) best case, whatever the input.
So, Setup() keeps the generated array as a source, and each call copies it into a working array before sorting:
public class InsertionSortBenchmarks
{
private readonly InsertionSortMethods _sortFunction = new();
private int[] _source = [];
private int[] _work = [];
[Params(100, 1_000, 10_000)]
public int Size { get; set; }
[Params("Random", "Sorted", "Reversed")]
public string Input { get; set; } = "Random";
[GlobalSetup]
public void Setup()
{
_source = Input switch
{
"Sorted" => InsertionSortMethods.CreateSortedArray(Size),
"Reversed" => InsertionSortMethods.CreateReversedArray(
InsertionSortMethods.CreateSortedArray(Size)),
_ => InsertionSortMethods.CreateRandomArray(Size)
};
_work = new int[Size];
}
[Benchmark]
public int[] SortArray()
{
_source.CopyTo(_work, 0);
return _sortFunction.SortArray(_work, _work.Length);
}
[Benchmark]
public int[] SortArrayRecursive()
{
_source.CopyTo(_work, 0);
return _sortFunction.SortArrayRecursive(_work, _work.Length);
}
}
Setup() runs before the timed calls of each method, once for every Size and Input combination. The copy adds the same O(N) to both methods, which hardly registers next to an O(N²) sort.
We stop at 10,000 elements because the recursive version crashes a little above that, as we saw in the recursive implementation section.
The class goes in its own file in our console app. We add the BenchmarkDotNet package to the app, start the class file with using BenchmarkDotNet.Attributes;, and call BenchmarkRunner.Run<InsertionSortBenchmarks>(); from its Program.cs, after using BenchmarkDotNet.Running;. Let’s run it in Release mode and look at the results:
| Method | Size | Input | Mean | Error | StdDev | |------------------- |------ |--------- |----------------:|--------------:|----------------:| | SortArray | 100 | Random | 3,033.8 ns | 38.75 ns | 36.24 ns | | SortArrayRecursive | 100 | Random | 1,543.6 ns | 9.23 ns | 8.63 ns | | SortArray | 100 | Reversed | 4,204.9 ns | 27.37 ns | 22.85 ns | | SortArrayRecursive | 100 | Reversed | 3,064.1 ns | 10.65 ns | 8.90 ns | | SortArray | 100 | Sorted | 125.8 ns | 1.64 ns | 1.53 ns | | SortArrayRecursive | 100 | Sorted | 201.1 ns | 0.80 ns | 0.75 ns | | SortArray | 1000 | Random | 192,639.9 ns | 688.62 ns | 644.13 ns | | SortArrayRecursive | 1000 | Random | 140,738.3 ns | 601.77 ns | 562.90 ns | | SortArray | 1000 | Reversed | 385,179.0 ns | 4,067.10 ns | 3,605.38 ns | | SortArrayRecursive | 1000 | Reversed | 258,689.8 ns | 1,294.09 ns | 1,080.63 ns | | SortArray | 1000 | Sorted | 1,299.2 ns | 2.57 ns | 2.14 ns | | SortArrayRecursive | 1000 | Sorted | 1,981.9 ns | 8.14 ns | 7.62 ns | | SortArray | 10000 | Random | 19,084,045.7 ns | 213,459.83 ns | 199,670.46 ns | | SortArrayRecursive | 10000 | Random | 12,783,999.1 ns | 42,653.81 ns | 39,898.40 ns | | SortArray | 10000 | Reversed | 40,137,948.8 ns | 799,431.26 ns | 1,614,890.70 ns | | SortArrayRecursive | 10000 | Reversed | 25,150,840.8 ns | 65,022.21 ns | 57,640.49 ns | | SortArray | 10000 | Sorted | 10,629.1 ns | 31.67 ns | 26.45 ns | | SortArrayRecursive | 10000 | Sorted | 21,537.9 ns | 48.21 ns | 40.26 ns |
On random numbers, SortArray() needs about 0.19 milliseconds for 1,000 elements and about 19 milliseconds for 10,000: a hundred times the time for ten times the elements, which is O(N²) in practice. At these sizes, reversed arrays take about twice as long as random ones, which matches the comparison counts, N(N − 1)/2 against roughly N²/4.
Sorted arrays are a different story. Both methods check each element once and finish 10,000 of them in about 11 to 22 microseconds, between about 600 and 1,800 times faster than the random case.
On random and reversed data, the recursive version is faster than the imperative one: about 12.8 against 19.1 milliseconds for 10,000 random numbers. Can you guess why?
The imperative SortArray() writes key back into the array after every single shift, so it writes twice as often as it needs to. When we counted for 2,000 random numbers, it made about 2 million writes against about 1 million in the recursive version. If we declare j before the inner loop, then move array[j + 1] = key; out of it and run it once, after the loop ends, the imperative version runs as fast as the recursive one. That is also how the InsertionSort method inside .NET’s own ArraySortHelper is written.
Recursion does cost something, though, and we see it on sorted data. There the work per element is tiny, so the extra method call per element is a visible part of it, and SortArrayRecursive() is slower than SortArray().
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.Â
Insertion sort is quick on small and nearly sorted arrays and slow on large random ones. For bigger arrays, shell sort keeps the same idea but first moves elements over long gaps, so they reach their place in fewer steps. If we use the recursive version, we need to keep our arrays well below its stack limit.
Tested with .NET 10.0.10, BenchmarkDotNet 0.15.8 and MSTest 4.5.2.
