How is the Knuth Sequence properly implemented for a shellsort in Java?

Question

Can someone please provide a simple working sample of a shellsort in Java that uses the Knuth Sequence? I looked in several places over the internet but can't find an explanation that works well for me. I understand shellsort on a conceptual level - as it's an insertion sort that is done over a gap that shrinks over time until reaching a gap of 1 - which then is essentially an insertion sort. However the Knuth sequence is (k * 3 - 1)/2 and a list of the first few gaps is usually represented as [1, 4, 13, 40, 121.. and so on].

My question is how would this be implemented? Is the starting gap actually 1, or is it the value generated by this sequence just before it is greater than the size of the list being sorted? If the gap started at 1, the purpose would be defeated if I am understanding shell sort correctly. Could someone pelease shed some light on this? I feel like I've missed something critical for understanding this thing.

Thanks in advance.

Answer 1

Late answer, but for any future onlookers too lazy to follow links from other answers or if the links break ...

This is a way to implement Knuth algorithm to find initial gap value as well as the remaining gap values in descending order:

// Find initial gap.
gap = 1; 
while gap < arrayLength {
  gap = gap * 3 + 1;
}

// Perform the main sorting logic...

// Somewhere within code, at the end
// of the main sorting logic, find next
// descending gap value.
gap /= 3;

The starting gap is not 1. It is the last highest number calculated before going over the length of the array being sorted.

The divide by 3 piece at the bottom basically goes in reverse order of the calculation that was performed in the while loop, in order to get the next gap value in the sequence, in descending order. This is done each time at the end of the main sorting logic.

Also, the formula is actually (3^k - 1) / 2 and NOT (3k - 1) / 2. The former will result in the correct sequence (1, 4, 13, 40, ...) and the latter an incorrect one.