E.g. h_i+i = 3h_i+1 ... 1093, 364, 121, 40, 13, 4, 1

Efficiency of Shellsort:

• depends on the sequence of h values
• suprisingly, Shellsort has not yet been fully analysed
• above sequence has been shown to be O(n^3/2)
• others have found sequences which are O(n^4/3)