public class ShellSort {

   public static final int[] GAPS = {1, 4, 10, 23, 57, 132, 301, 701};
   
   public static void shellSort(int[] a) {
      for (int gapIndex = GAPS.length - 1; gapIndex >= 0; gapIndex--) {
         int increment = GAPS[gapIndex];
         if (increment < a.length)
            for (int i = increment; i < a.length; i++) {
               int temp = a[i];
               for (int j = i; j >= increment && a[j - increment] > temp; j -= increment) {
                  a[j] = a[j - increment];
                  a[j - increment] = temp;
               }
            }
      }
   }
   
   public static void printArray(String message, int [] a){
      System.out.print(message + ": ");
      for (int current:a)
         System.out.print(" " + current);
      System.out.println(); System.out.println();
   }
   

   /**
    * @param args
    */
   public static void main(String[] args) {
      int SIZE = 31;
      int [] nums = new int[SIZE];
      for (int i=0; i<SIZE; i++) {
         nums[i] = (SIZE/2 + 5*i) % SIZE;
      }
      printArray("Before sort", nums);
      shellSort(nums);
      printArray("After sort", nums);
   }

}