Re: Quick Sort Median of Three worst case

["Wendy E. McCaughrin" <wemccaug@bluestem.prairienet.org>]

In comp.lang.c goms <gomskams@yahoo.co.uk> wrote:
: Hi,

: I would like to know the running time of the Median of Three routine
: version Quick Sort for the following input

: (a)      2, 3, 4, ..,N-1, N, 1

: What is the running time for the following input

: (b)      1, N, N-1, ....., 4, 3, 2

: Is the above said inputs (a) and (b) the worst case? and is the
: running time is O(N^2) ?

 It depends upon what is meant by "running time". QuickSort basically has to
 perform three operations at each iteration/recursion: selection of a pivot,
 comparison of elements to the pivot from its left and right, and transposi-
 tions when out of order. 
 In (a), the first iteration would (using Median of 3) choose 2, 1, N/2 and
 choose N/2 as the pivot, then compare 2 and 1 to it and transpose them, and 
 then compare about N/2 - 1 remaining elements left of the pivot to it, only
 to find them in sort.  Thus no more transpositions in that first iteration
 would occur, and no further transpositions would occur in future iterations.
 But pivots would still get chosen and comparisons of elements made against 
 it, so it appears that O(n*lg(n)) comparisons would occur. (The common case
 of QuickSort said to perform O(n^2) on nearly-sorted lists is an artifact of
 always choosing some minimum or maximum element from the left or right on
 each partition.)

 In (b), the first transposition is avoided but -- since every element com-
 pared to the pivot would be out of sort, the number of transpositions as
 well as comparisions appears to be O(n*lg(n)).

 In both cases -- since Median of 3 is used to select the pivot from sorted
 lists -- the pivot manages to bisect the least into two equal halves, thus
 helping to ensure O(lg(n)) iterations from original list to smallest parti-
 tion.