How to use the empirically derived increment for shell sort?

Question

As per the Wikipedia article, I am trying to implement Shell sort with the empirically derived increments to perform the h-sort:

1,4,10,23,57,132,301,701

Presently, I am using h = 3*h + 1 to perform the sort, here is my implementation:

    public class Solution
{
    private static final int arr[] = {9,4,5,1,2,8,7,6,12,45,21,34,1,2,3};
    public static void main(String[] args)
    {
        int N = arr.length;
        int h = 1;
        while(h<N/3)
            h = 3*h + 1;
        while(h>=1)
        {
            for(int i=h;i<N;i++)
            {
                for(int j=i;j>=h && arr[j-h]>arr[j];j-=h)
                {
                    int temp = arr[j-h];
                    arr[j-h] = arr[j];
                    arr[j] = temp;
                }
            }
            h/=3;
        }

        for(int x:arr)
            System.out.println(x);

    }
}

Now, this does the task well. But the question is, if I were to implement the shell sort by using the empirically derived sequence to perform the h sort, how should I choose which increment I must use based on the size of array?

Answer 1

Store empirically derived sequence in array and find the last element of this array that is smaller than data array size.

For example, if data size is 500, you have to get 301 as the first step