/*
 *  ShellSort
 *
 *  20.11.1998, implemented by Michael Neumann (neumann@s-direktnet.de)
 */

# ifndef __SHELLSORT_HEADER__
# define __SHELLSORT_HEADER__

# include <algorithm>

template <class itemType, class indexType=int>
void ShellSort(itemType a[], indexType l, indexType r)
{
	static indexType i, j, h;
   static itemType v;

   for(h=1; h<=(r-l)/9; h=3*h+1);
  	for(; h>0; h/=3) {
     	for(i=l+h; i<=r; ++i) {
        	for(j=i-h, v=a[i]; j>=l && a[j]>v; a[j+h]=a[j], j-=h);
           a[j+h] = v;
      	}
   }
}

# endif