A visualization of Shell Sort on different gap sequences Most of these gap sequences have a best case of O(n log n), except Pratt's sequence, which has a best case of O(n log^2 n) Worst Cases: Original Gaps: O(n^2) Hibbard Gaps: O(n^1.5) Frank & Lazarus Gaps: O(n^1.5) Knuth Gaps: O(n^1.5) Pratt Gaps: O(n log^2 n) Sedgewick Gaps (1982): O(n^(4/3)) Incerpi & Sedgewick Gaps: O(n^(1+sqrt(8 ln(5/2)/ln(n)))) Sedgewick Gaps (1986): O(n^(4/3))
