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: