Accidently discovered the worst case. Sounds really cool. I wonder if anyone else has figured this out before? This happens when using the default shell constants (divide the gap by two), because the binary is sorted in a binary reverse (2-ary reverse) A shellsort with knuth, hibbard, ciura.. gap sequences would probably sort this quickly, but I assume there would be a similar pattern for every gap sequence. Visualizer: svis4.glitch.me Alternative link: svis4.playcode.io (Use if the first link is blocked)
Shell proposed this algorithm, with these gaps, in 1959. By 1960, improved gap sequences which avoided precisely this problem were already being proposed - Papernov, Hibbard, etc. Basically, one must avoid a pure geometric sequence with integer base, and these early proposals (up to the early 1980s) were normally for an integer geometric sequence that was offset by a constant; for example, Hibbard's sequence is just the Mersenne numbers, 2^k-1. This includes Knuth's recommendation from the 1970s: (3^k+1)/2, no greater than N/3. Pratt proved that Shell's original sequence had worst-case complexity O(N^2), and that these conventional alternatives were O(N^3/2) worst-case. In 1971 he showed that using the 3-smooth numbers (2^p * 3^q) reduced the asymptotic complexity to O(N log^2 N). However, because this involves a large number of passes over the data, the average-case performance of this version is significantly worse than the conventional sequences. It's still an interesting way to construct a sorting network that has O(log^2 N) layers, so this is still vaguely relevant to parallel computing (eg. on GPUs). The next advance was by Sedgewick, who showed that the sum of two near-geometric sequences yielded better results, both asymptotically and in practice, than a single one as previously used. One such sequence is hilariously easy to compute: start with a=(4
![SahBabii - Viking [Official Music Video]](http://i.ytimg.com/vi/D37cL92JX0I/mqdefault.jpg)
Accidently discovered the worst case. Sounds really cool. I wonder if anyone else has figured this out before?
This happens when using the default shell constants (divide the gap by two), because the binary is sorted in a binary reverse (2-ary reverse)
A shellsort with knuth, hibbard, ciura.. gap sequences would probably sort this quickly, but I assume there would be a similar pattern for every gap sequence.
Visualizer: svis4.glitch.me
Alternative link: svis4.playcode.io
(Use if the first link is blocked)
Shell proposed this algorithm, with these gaps, in 1959. By 1960, improved gap sequences which avoided precisely this problem were already being proposed - Papernov, Hibbard, etc. Basically, one must avoid a pure geometric sequence with integer base, and these early proposals (up to the early 1980s) were normally for an integer geometric sequence that was offset by a constant; for example, Hibbard's sequence is just the Mersenne numbers, 2^k-1. This includes Knuth's recommendation from the 1970s: (3^k+1)/2, no greater than N/3.
Pratt proved that Shell's original sequence had worst-case complexity O(N^2), and that these conventional alternatives were O(N^3/2) worst-case. In 1971 he showed that using the 3-smooth numbers (2^p * 3^q) reduced the asymptotic complexity to O(N log^2 N). However, because this involves a large number of passes over the data, the average-case performance of this version is significantly worse than the conventional sequences. It's still an interesting way to construct a sorting network that has O(log^2 N) layers, so this is still vaguely relevant to parallel computing (eg. on GPUs).
The next advance was by Sedgewick, who showed that the sum of two near-geometric sequences yielded better results, both asymptotically and in practice, than a single one as previously used. One such sequence is hilariously easy to compute: start with a=(4
@Kromaatikse I made my own sequence which is approx n log n (improved version of sedgewick)
In-place radix sort
Imagine doing a worst case with bogo