On the average‐case complexity of Shellsort. Issue 2 (13th November 2017) - Vitányi, Paul
Abstract: We prove a lower bound expressed in the increment sequence on the average‐case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it could be checked. A special case of this lower bound yields the general Jiang‐Li‐Vitányi lower bound. We obtain new results, for example, determining the average‐case complexity precisely in the Yao‐Janson‐Knuth 3‐pass case.