// Complete sorting algorithm by given invariant of outer loop

using System;

​

public class Program

{

    void swap(int[] a, int i, int j)

    {

        int t = a[i];

        a[i] = a[j];

        a[j] = t;

    }

    void sort(int[] a)

    {

        int k = 1;

​

        // invariant: first k elements of the array are ordered

        while (k != a.Length)

        {

            int j = k;

            // invariant: segment a[j..k-1] is ordered and

            //            segment a[0..j-1] is ordered

            while (j > 0 && a[j - 1] > a[j])

            {

                swap(a, j - 1, j);

                j--;

            }

            // segment a[0..j-1] is empty or [aj-1]<=a[j] =>

            // segment a[0..k] is ordered => 

            // first k+1 elemets of the array are ordered

            k++;

            // first k elemets of the array are ordered

        }

    }

    public static void Main(string[] args)

    {

        int[] number = { 89, 76, 45, 92, 67, 12, 99 };

        Console.WriteLine("before sorting");

        foreach (int num in number)

            Console.Write("\t {0}", num);

        Program ob = new Program();

        ob.sort(number);

        Console.WriteLine("\nafter sorting");

        foreach (int num in number)

            Console.Write("\t {0}", num);

    }

}