# Insertion Sort Algorithm in C#

# 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.

Join the DZone community and get the full member experience.

Join For FreeHortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.

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²).

**Conclusion**

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.

Hortonworks Community Connection (HCC) is an online collaboration destination for developers, DevOps, customers and partners to get answers to questions, collaborate on technical articles and share code examples from GitHub. Join the discussion.

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.linkDescription }}

{{ parent.urlSource.name }}