TAOCP 5.2.2 Exercise 26
The worst-case running time of Program Q (Quicksort with a cutoff to straight insertion for subfiles of size \(\le M\)) is achieved by an input that forces the maximum number of partitioning stages wh...
Section 5.2.2: Sorting by Exchanging
Exercise 26. ▶ [M24] Construct an input file that makes Program Q go even more slowly than it does in exercise 25. (Try to find a really bad case.)
Verified: no
Solve time: 14m35s
Solution
The worst-case running time of Program Q (Quicksort with a cutoff to straight insertion for subfiles of size (\le M)) is achieved by an input that forces the maximum number of partitioning stages while also maximizing the work done by the final insertion sort.
The sorted input (1,2,\ldots,N) analysed in Exercise 25 yields a partitioning chain of length (N-M) (quantities (A = N-M), (C = \sum_{k=M+1}^{N}(k+1)), (S = 2(N-M))) but the final subfile of size (M) is already in order, so insertion sort does minimal work ((D = M-1), (E = 0)).
A strictly slower input is the completely reverse sorted file
[ K_1 = N,; K_2 = N-1,; \ldots,; K_N = 1. ]
On this input the first element of every subfile encountered during the sort is the largest key in that subfile.
During partitioning (Hoare's scheme) the (j) pointer stops immediately while the (i) pointer scans the whole subfile; no exchanges occur ((B = 0)).
The partition yields a left subfile of size (n-1) (which is again reverse sorted) and an empty right subfile.
The algorithm therefore performs exactly the same number of partitioning stages (A = N-M), the same number of comparisons (C), and the same stack operations (S) as for the sorted input.
When the subfile size finally drops to (M), the remaining (M) elements are (M, M-1, \ldots, 1) , a completely reverse sorted array.
Straight insertion on a reverse sorted array of size (M) requires the maximum possible number of comparisons and exchanges:
[ D = \frac{M(M+1)}{2} - 1,\qquad E = \frac{M(M-1)}{2}. ]
These values are strictly larger than the (D = M-1,; E = 0) obtained for the sorted input of Exercise 25.
Since the MIX running time of Program Q is a positive linear combination of the quantities (A,B,C,D,E,S), the reverse sorted file makes the program run slower than the sorted file.
\boxed{\text{The input file } N,; N-1,; \ldots,; 1 \text{ (reverse order) is a worst-case input.}}
Notes
Any input that produces a chain of (N-M) partitioning stages (i.e. the pivot is always the extreme element) and leaves a final subfile of size (M) in reverse order is equally bad.
The simplest such file is the one given above.