Shellsort - Wikipedia (FazBrowse)

2) (worst known worst case gap sequence) O(''n'' log2''n'') (best known worst case gap sequence)<ref name=\"Pratt\">{{Cite book\n |last=Pratt\n |first=Vaughan Ronald |author-link=Vaughan Ronald Pratt\n |year=1979\n |publisher=Garland\n |title=Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences)\n |url=https://apps.dtic.mil/sti/pdfs/AD0740110.pdf\n |archive-url=https://web.archive.org/web/20210907132436/https://apps.dtic.mil/sti/pdfs/AD0740110.pdf\n |url-status=live\n |archive-date=7 September 2021\n |isbn=978-0-8240-4406-0}}</ref>"},"best-time":{"wt":"O(''n'' log ''n'') (most gap sequences) O(''n'' log2''n'') (best known worst-case gap sequence)<ref>{{cite web |title=Shellsort & Comparisons |url=http://www.cs.wcupa.edu/rkline/ds/shell-comparison.html |access-date=14 November 2015 |archive-date=20 December 2019 |archive-url=https://web.archive.org/web/20191220040546/https://www.cs.wcupa.edu/rkline/ds/shell-comparison.html |url-status=dead }}</ref>"},"average-time":{"wt":"depends on gap sequence"},"space":{"wt":"О(''n'') total, O(1) auxiliary"},"optimal":{"wt":"No"}},"i":0}}]}'>

Shellsort

a11

⌊N2k⌋

2⌊N2k+1⌋+1

2k−1

2k+1, prefixed with 1

2p3q (3-smooth numbers)

3k−12, not greater than Θ(N32)

Knuth, 1973, based on Pratt, 1971

A036569

O(N1+8ln⁡(5/2)ln⁡(N))

Incerpi & Sedgewick, 1985, Knuth