Why is the sequence 1,4,13,40,121... more efficient then 1,2,4,8,16... when insertion-sorting?

1,4,13,40,121...((3 * n) + 1) works slightly more e开发者_如何学Gofficiently than 1,2,4,8,16...(2 * n) when inserting random numbers to a sorting algorithm.

Why is this? Is it anything to do with threading?

Thanks.

It is well known that the shell sort increment steps of 2^k, 2^(k-1), ..., 1 are one of the worst. For instance, you only compare the elements at the odd positions, with the ones at the even positions only at the last step!

The other steps seem to be (3^k -1)/2 (and not 3n+1) and don't suffer from problems like the even/odd issue. That is not a proof, but we might expect this to be better than powers of 2.

If you are looking for mathematical analysis, Shell Sort is well known for giving mathematicians a hard time.

I didn't find any analysis of your sequence in Sedgewick's paper here. Perhap one of Knuth's books has it.

Good luck.

btw, why do you ask about threading?