Shellsort With Three Increments
December 15, 2015
It was a dreary Sunday in St Louis, unseasonably warm, but it rained all day and felt much colder than the actual air temperature, so I sat down to read Donald Knuth’s article, with Svante Janson, Shellsort With Three Increments. After sixteen pages, Janson and Knuth conjecture but do not prove that the gap sequence (h, g, 1) with h ≈ √n and g ≈ √h and h coprime to g leads to time complexity O(n3/2).
Your task is to implement shellsort, as we did in a previous exercise, and test the Janson/Knuth conjecture. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python. For N > 1000 the conjecture seems to hold.
from fractions import gcd from math import sqrt from timeit import repeat def shellsort(array, gaps=None): n = len(array) if gaps is None: h, g = round(sqrt(n)), round(sqrt(sqrt(n))) while gcd(h, g) != 1: h += 1 gaps = (h, g, 1) for gap in gaps: for i in range(gap, n): val = array[i] j = i while j >= gap and array[j - gap] > val: array[j] = array[j - gap] j -= gap array[j] = val if __name__ == "__main__": for n in range(7): N = 10 ** n setup = "import random;from __main__ import shellsort;" setup += "data = cdata = list(range(" + str(N) + "));" setup += "random.shuffle(data)" stmt = "shellsort(data)" print("{:8d} {:12g} {:12g}".format( N, N ** 1.5 / 3000000, min(repeat(stmt, setup, number=6)))) """ N cN^3/2 time 1 3.33333e-07 3.07887e-05 10 1.05409e-05 0.000104681 100 0.000333333 0.000972409 1000 0.0105409 0.0162739 10000 0.333333 0.364905 100000 10.5409 10.0037 1000000 333.333 322.088 """