package sorting;

import java.util.Random;


public class ShellHibbard {
	
	public static <AnyType extends Comparable<? super AnyType>> void shellHibbard(AnyType[] a) {
		double k = Math.floor(Math.log(a.length + 1) / Math.log(Math.E));
		int inc = (int) Math.pow(2.0, k) - 1;
		while (inc > 0) {
		    for (int i = inc; i < a.length; i++) {
		    	AnyType temp =  a[i];
		        int j = i;
		        while (j >= inc && a[j-inc].compareTo(temp) > 0) {
		            a[j] = a[j - inc];
		            j -= inc;
		        }
		        a[j] = temp;
		    }
		    inc = (int) Math.pow(2.0, --k) - 1;
		}   
		return;
	}
     
}