#ifndef SHELL_SORT_HH
#define SHELL_SORT_HH

template<typename ItemType>
void ShellSort(ItemType* array, unsigned size)
{
    const unsigned hmax = size/9;
    unsigned h;
    for(h = 1; h <= hmax; h = 3*h+1);
    for(; h > 0; h /= 3)
    {
        for(unsigned i = h; i < size; ++i)
        {
            ItemType v = array[i];
            unsigned j = i;
            while(j >= h && v < array[j-h])
            {
                array[j] = array[j-h];
                j -= h;
            }
            array[j] = v;
        }
    }
}

#endif