Insertion Sort Algorithm in C#

DZone 's Guide to

Insertion Sort Algorithm in C#

A common sorting algorithm is the Insertion Sort. We take a look at what it is using C# and how it performs.

· Big Data Zone ·
Free Resource

In this article, I am going to explain the Insertion Sort algorithm. Insertion Sort is based on the idea of consuming one element from an input array in each iteration to find its correct position in a sorted array. This algorithm is efficient for smaller datasets.

First, I am going to explain the Insertion Sort algorithm. Then, I will provide some C# code to execute it.

The Insertion Sort Algorithm

Insertion Sort compares the current element with the largest value in a sorted array. If the current element is smaller, then the algorithm finds its correct position in the sorted array and moves the element to that position. Otherwise, if the current element is greater, it leaves the element in its place and moves on to the next element.

To place the element in its correct position in a sorted array, all the elements larger than the current element are shifted one place ahead. Thus, the sorted array will grow at each iteration.

Let's understand this with the help of an example.

Let's take the input array as 8 5 7 3 1.

The sorted output for this array is 1 3 5 7 8.

Iterations Input Array Sorted Array Unsorted Array
Iteration 1  8 5 7 3 1   8 5 7 3 1
Iteration 2 8 5 7 3 1 5 8 7 3 1
Iteration 3 5 8 7 3 1 5 7 8 3 1
Iteration 4 5 7 8 3 1 3 5 7 8 1
Iteration 5 3 5 7 8 1 1 3 5 7 8

Hence, we got the sorted array in iteration 5.

Time Complexity

Every element is compared to every other element of the sorted array. Hence, the complexity of Insertion Sort is O(n²).


In this tutorial, we learned about the Insertion Sort algorithm and its implementation using C#.

You can download the source code from here.

You can find my other articles on algorithms here.

algorithms, big data, c#, data analytics, insertion sort, sorted array, tutorial

Published at DZone with permission of Ankit Sharma , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}