# Insertion sort

Insertion sort is a sorting algorithm in which all elements of an array are scanned in turn, with each element being placed in an appropriate place among previously ordered values.

## Description of the insertion sorting algorithm

The algorithm for inserting sorting is as follows:

• at the beginning of the work, the ordered part is empty;
• add to the sorted area the first element of the array of unordered data;
• go to the next element in unsorted data, and find the correct position in the sorted part of the array, thereby expanding the range of ordered data;
• repeat the previous step for all remaining elements.

## Implementation of sorting by inserts

``````using System;

class program
{
// element exchange method
static void Swap(ref int e1, ref int e2)
{
var temp = e1;
e1 = e2;
e2 = temp;
}

// sort by inserts
static int[] InsertionSort(int[] array)
{
for (var i = 1; i < array.Length; i++)
{
var key = array[i];
var j = i;
while ((j > 1) && (array[j - 1] > key))
{
Swap(ref array[j - 1], ref array[j]);
j--;
}

array[j] = key;
}

return array;
}

static void Main(string[] args)
{
Console.WriteLine("Sort by inserts");
Console.Write("Enter elements of the array:");
var parts = Console.ReadLine().Split(new[] { "", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);
var array = new int[parts.Length];
for (int i = 0; i < parts.Length; i++)
{
array[i] = Convert.ToInt32(parts[i]);
}

Console.WriteLine("Ordered array: {0}", string.Join(",", InsertionSort(array)));

Console.ReadLine();
}
}
``````

The result of the program: