%0 Journal Article %1 poonen93 %A Poonen, B. %D 1993 %J Journal of Algorithms %K algorithm shellsort sorting %N 1 %P 101--124 %R 10.1006/jagm.1993.1032 %T The Worst Case in Shellsort and Related Algorithms %V 15 %X We show that sorting a sufficiently long list of length N using Shellsort with m increments (not necessarily decreasing) requires at least Nl+c/√m comparisons in the worst case, for some constant c > 0. For m ≤ (log N/log log N)2 we obtain an upper bound of the same form. We also prove that Ω(N(log N/log log N)2) comparisons are needed regardless of the number of increments. Our approach is general enough to apply to other sorting algorithms, including Shaker-sort, for which an even stronger result is proved.

@article{poonen93, abstract = {We show that sorting a sufficiently long list of length N using Shellsort with m increments (not necessarily decreasing) requires at least Nl+c/√m comparisons in the worst case, for some constant c > 0. For m ≤ (log N/log log N)2 we obtain an upper bound of the same form. We also prove that Ω(N(log N/log log N)2) comparisons are needed regardless of the number of increments. Our approach is general enough to apply to other sorting algorithms, including Shaker-sort, for which an even stronger result is proved.}, added-at = {2016-10-29T15:57:26.000+0200}, author = {Poonen, B.}, biburl = {https://www.bibsonomy.org/bibtex/246e65757bfd06ac9cf1c10b3d4474f64/ytyoun}, doi = {10.1006/jagm.1993.1032}, interhash = {3ff413c89ba63553b4bc2d1872ac75d6}, intrahash = {46e65757bfd06ac9cf1c10b3d4474f64}, issn = {0196-6774}, journal = {Journal of Algorithms}, keywords = {algorithm shellsort sorting}, number = 1, pages = {101--124}, timestamp = {2016-10-29T15:57:26.000+0200}, title = {The Worst Case in {Shellsort} and Related Algorithms}, volume = 15, year = 1993 }