Shell sort

I was watching a COMP1927 lecture online (yes, this is what I do for fun), and remembered something that I was going to post but hadn’t gotten around to yet.

I’ve been fiddling with Shell sort gap sequences a bit. The idea I was working on was that a good gap sequence would consist mostly of numbers that are mutually prime; it seems like numbers with common factors would lead to sub-sorts that cover a lot of the same ground, for the same sort of reason that hash functions don’t work well if the hash value is modulo a number that’s some kind of factor in the data. (I don’t have any particularly good theory to back this up; it’s just intuition.)

Apparently (or “wikily”, a word we invented recently to mean “according to Wikipedia”) a geometric sequence that increases by a factor of 2.2 makes a good Shell sort sequence. So I tried out a sequence that:

  • consists of products of the first n primes (if you write out the prime factors of each number in the sequence, each of the first n primes occurs exactly once); and
  • increases by approximately a factor of 2.2.

Finding the best such sequence (the one with a ratio between pairs of elements that’s close to 2.2, by one of a handful of definitions of “close”) is a task in itself. Computing the sequence for n=16 took nearly a week, and the result is:

1, 2, 5, 11, 23, 53, 119, 377, 817, 1739, 3813

or, as products of primes:

1, 2, 5, 11, 23, 53, 7×17, 13×29, 19×43, 37×47, 3×31×41

And, empirically, it does pretty well. Not as well as Ciura’s sequence (1, 4, 10, 23, 57, 132, 301, 701, 1750), but pretty close. I don’t have the test-run data on hand, but I might put it in a follow-up post later.

No comments

No comments yet. Be the first.

Leave a reply