3.8 EXTERNAL POLYPHASE MERGE SORT 95
PivotValue = list[ first ]
lower = first
upper = last+1
do
do upper = upper - 1 until list[upper] ≤ PivotValue
do lower = lower + 1 until list[lower] ≥ PivotValue
Swap( list[ upper ], list[ lower ] )
until lower ≥ upper
// undo the extra exchange
Swap( list[ upper ], list[ lower ] )
// move pivot point into correct place
Swap( list[ first ], list[ upper ] )
return upper
(Note: This algorithm requires one extra list location at the end to hold a
special sentinel value that is larger than all of the valid key values.)
a. Do Question 1 using this alternative method for PivotList.
b. Do Question 2 using this alternative method for PivotList.
c. What operation is done significantly less frequently for this version of
PivotList?
d. How many key comparisons does the new PivotList do in the worst
case for a list of N elements? (Note: It is not N 1.) How does this affect
the overall worst case for quicksort?
- How many comparisons will Quicksort do on a list of N elements that all
have the same value?
- What is the maximum number of times that Quicksort will move the
largest or smallest value?
3.8 External Polyphase Merge Sort
In some cases, a list that needs to be sorted may be so large that it cannot be
held in memory at one time. You should note that even though our sorting
algorithms have only been concerned with placing keys in the correct order, it
is assumed that those keys are connected to entire records of information. You
should see that in many instances, the size of the full record will be signifi-
cantly larger than the size of the key. In some instances, the record size is so
significant that the process of swapping two records becomes so time consum-
ing that the efficiency of a sorting algorithm is both the number of compari-
sons and the number of swaps.
