using System;

​

class BinaryInsertion

{

    static void BinaryInsertionSort(int[] array)

    {

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

        {

            int key = array[i];

            int j = i - 1;

            while (j >= 0 && array[j] > key)

            {

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

                j--;

            }

            array[j + 1] = key;

        }

    }

​

    static void Main()

    {

        int[] arr = { 37, 23, 0, 17, 12, 72, 31 };

        BinaryInsertionSort(arr);

        Console.WriteLine(" Sorted array: " + string.Join(", ", arr));

    }

}