Average-Case Complexity of Shellsort

We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a p-pass Shellsort for any incremental sequence is \Omega\Gamma pn 1+ 1 p ) for all p log n. Using similar arguments, we analyze the average-case complexity of several other sorting algorithms. 1 Introduction The question of a nontrivial general lower bound (or upper bound) on the average complexity of Shellsort (due to D.L. Shell [15]) has been open for about four decades [7, 14]. We present such a lower bound for p-pass Shellsort for every p. Shellsort sorts a list of n elements in p passes using a sequence of increments h 1 ; : : : ; h p . In the kth pass the main list is divided in h k separate sublists of length n=h k , where the ith sublist consists of the elements at positions j, where j mod h k , of the main list (i = 1; : : : ; h k ). Every sublist is sorted using a straightforward insertion sort. The efficiency of the method is gove..