## 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.

Pages: 1 2

### One Response to “Shellsort With Three Increments”

1. Paul said

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
"""
```