using System;

public class Program

{

    public static void Main()

    {

         int[] array = new int[] { 22, 11, 99, 88, 9, 7, 42 };

        Console.WriteLine(string.Format("Array after sorting: {0}" , string.Join(",", InsertionSort.Sort(array))));

        int[] array2 = new int[] { 1, 11, -5, 88, 9, 223, 2 };

        Console.WriteLine(string.Format("Array after sorting: {0}" , string.Join(",", InsertionSort.Sort(array2))));

    }

    static class InsertionSort

    {

        static void Insert(int[] array, int rightIndex, int value)

        {

            int j;

            for (j = rightIndex; j >= 0 && array[j] > value; j--)

            {

                array[j + 1] = array[j];

            }

            array[j + 1] = value;

        }

​

        public static int[] Sort(int[] array)

        {

            for (var i = 1; i< array.Length;i++)

            {

                Insert(array, i-1, array[i]);

            }

​

            return array;

        }

    }

}