We prove a lower bound expressed in the increment sequence on the average-case complexity (number of inversions which is proportional to the running time) of Shellsort. This lower bound is sharp in every case where it could be checked. We obtain new results e.g. determining the average-case complexity precisely in the Yao-Janson-Knuth 3-pass case.
Cornell University Library
arXiv.org e-Print archive

Vitányi, P. (2015). On the Average-Case Complexity of Shellsort. arXiv.org e-Print archive. Cornell University Library .