8.5.4 The Worst and Best Cases

To analyze the total time of partition, recall that each execution takes time O(length of the component array it is called to work on). Since the length of a component is at most n, with partition being invoked at most n times, total time is at most O(n2). Hence quicksort has a worst-case time O(n2). You should convince yourself that the worst case occurs whenever the initial array is in sorted or reverse sorted order.

The best case (fastest execution) actually occurs when the partitioning entry returned by partition splits the array in half. In this case, partition is called to work on one component array of length n, two component arrays of length n/2, four component arrays of length n/4, . . . , 2k component arrays of length n/2k, etc. By an argument similar to the worst-case analysis of the binary search, about 1g n such calls will be made to partition. Its total time will then be O(n 1g n).

While the worst-case time for quicksort is poor, its best-case time is fast?/FONT>in fact, better than heapsort. The average time for quicksort is also O(n 1g n). This assumes that each ordering of the n entries is equally likely to appear in the initial array. Evidently, cases differing significantly from the best occur rarely, and this is why quicksort is aptly named.

The storage requirements for quicksort, beyond the initial array, are a few variables plus the stack depth. Since the larger of each generated component array problem is stacked, the next problem to be stacked must have length at most one-half the current top stack entry length. For example, in the preceding section, note that when (6,7) was placed on the stack, its length was no greater than half the length of the preceding stack component (1,4). Again, by an argument similar to the worst-case binary search analysis, at most O(1g n) such problems can appear on the stack at any time, so the storage requirements for quicksort are O(1g n). Thus, quicksort, while faster on the average than heapsort, does not have the guaranteed worst-case O(n 1g n) time of heapsort. Moreover, quicksort requires additional storage O(1g n) to achieve its faster average time.

For smaller values of n, the simpler sorts, like the insertion sort, will be even faster than quicksort. Of course, if the initial array is known to be nearly sorted, the insertion sort will be faster anyway. Clearly, one way to speed up quicksort is to modify it by using a faster sort, such as insertion sort, when small component arrays are encountered. It is also possible to enhance the performance of quicksort by taking more care in the selection of the entry to be used as a basis by partition. Instead of taking the first entry of a component as the basis, the median of three entries may be selected, or an entry may be selected at random.