Fastest gap sequence for shell sort?

algorithm performance sorting shellsort
Sawyer picture Sawyer · Mar 29, 2010 · Viewed 19.1k times · Source

According to Marcin Ciura's Optimal (best known) sequence of increments for shell sort algorithm, the best sequence for shellsort is 1, 4, 10, 23, 57, 132, 301, 701..., but how can I generate such a sequence? In Marcin Ciura's paper, he said:

Both Knuth’s and Hibbard’s sequences are relatively bad, because they are defined by simple linear recurrences.

but most algorithm books I found tend to use Knuth’s sequence: k = 3k + 1, because it's easy to generate. What's your way of generating a shellsort sequence?

Answer

John Feminella picture John Feminella · Mar 29, 2010

Ciura's paper generates the sequence empirically -- that is, he tried a bunch of combinations and this was the one that worked the best. Generating an optimal shellsort sequence has proven to be tricky, and the problem has so far been resistant to analysis.

The best known increment is Sedgewick's, which you can read about here (see p. 7).

Related questions

When should we use Radix sort?

It seems Radix sort has a very good average case performance, i.e. O(kN): http://en.wikipedia.org/wiki/Radix_sort Yet it seems like most people are still using Quick Sort - why is this?

Read More
Fast algorithm implementation to sort very small list

This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small list of numbers (integers), 4 or 8 elements, that need to be sorted, fast. what would be the …

Read More
What are the rules for the "Ω(n log n) barrier" for sorting algorithms?

I wrote a simple program that sorts in O(n). It is highly memory inefficient, but that's not the point. It uses the principle behind a HashMap for sorting: public class NLogNBreak { public static class LinkedListBack { public LinkedListBack(int val){ …

Read More