/**
*
* Implemention of a classical sorting algorithm, provided for
* use in testing and debugging exercises.
*/

public class MySort {

  public static void sort ( int[] A ) {

    for (int i=1; i < A.length; i++) {

     /*
     * Loop Invariant:
     * a) The entries of A have been rearranged but are
     * otherwise unchanged
     * b) i is an integer such that 1 <= i <= A.length
     * c) The entries of A[0], A[1], ..., A[i-1] are
     *    sorted in nondecreasing order -  that is,
     *    A[h] <= A[h+1] for every integer h such that
     *    0 <= h <= i-2
     * Loop Variant: A.length - i
     */ 

        int j = i-1;

        while ((j >= 0) && (A[j] > A[j+1])) {

        /*
        * This inner loop moves the entry that is initially
        * in position A[i] toward the front until the entries of
        * A[0], A[1], ..., A[i] are in sorted order
        *
        * Parts (d), (e), (f) and (g) of the following
        * loop invariant say, essentially, that this
        * part of the array is almost sorted: only
        * A[j+1] is smaller than the entry in front of it,
        * and moving this entry forward by one or more
        * positions will sort this part of the array.
        *
        * Loop Invariant:
        * a) The entries of A have been rearranged but are
        *     otherwise unchanged 
        * b) i is an integer such that 1 <= i <= A.length
        * c) j is an integer such that 0 <= j <= i-1 
        * d) A[h] <= A[h+1] for every integer h such
        *    that 0 <= h <= j-1
        * e) A[h] <= A[h+1] for every integer h such that
        *    j+1 <= h <= i-1
        * f) if j < i-1 then A[j] <= A[j+2]
        * g) A[j] > A[j+1]
        * Loop Variant: j+1
        */

          int temp = A[j];
          A[j] = A[j+1];
          A[j+1] = temp;
          j--;

        };

      };

    } 

}