[22] Consider two variants of p-pass Shellsort. In each pass, instead of fully sorting every sublist, we make only one pass of Bubblesort, or two such passes in opposite directions, for every sublist. In both cases the sequence may stay unsorted, even if the last increment is 1. A final phase, a straight insertion sort, is required to guaranty a fully sorted list.

(a) Prove an Ω(n2/2p) lower bound on the average-case running time for the 1-pass variant of p-pass Shellsort.

(b) Prove an Ω(n2/4p) lower bound on the average-case running time for the 2-pass variant of p-pass Shellsort.

Comments. The 1-pass variant of Shellsort is called Dobosiewicz sort by D.E. Knuth [The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, 1973, Exercise 5.2.1.40, page 105]. Source:

[W. Dobosiewicz, Inform. Process. Lett. 11:1(1980), 5–6]. The 2-pass variant, proposed by J. Incerpi and R. Sedgewick [Inform. Process. Lett.

26:1(1980), 37–43], is called Shakersort. Solutions for both

(a) and (b)

were given by B. Brejov´a [Inform. Process. Lett., 79:5(2001), 223–227].