/* modified from Robert Sedgewick's website */

typedef int itemType;

shellsort(itemType a[], int l, int r)
{ int i, j, h, k; itemType v;
 int incs[16] = { 1391376, 463792, 198768, 86961, 33936,
		  13776, 4592, 1968, 861, 336, 
		  112, 48, 21, 7, 3, 1 };
 for ( k = 0; k < 16; k++)
   for (h = incs[k], i = l+h; i <= r; i++)
     { 
       v = a[i]; j = i;
       while (j > h && a[j-h] > v)
	 { a[j] = a[j-h]; j -= h; }
       a[j] = v; 
     } 
}