Consider the following quicksort-like sorting algorithm.
Pick two elements of the list. Partition based on both of the elements. So the elements smaller than both are to the left, the elements in between are in the middle, and the elements larger than both are to the right.
(a) Given a brief English description of how you would partition. Write high-level pseudo-code for this algorithm. Try to minimize the number of comparisons. Your algorithm should use a linear number of comparisons.
(b) How many comparisons does the partition algorithm use in the worst case? Justify.
(c) How many comparisons does the partition algorithm use on average? Just get the high order term. Justify informally.
(d) Assume that the two partition elements always partition exactly into thirds. Write a recurrence for the number of comparisons. Solve this recurrence using constructive induction. Just get the high order term exactly.
(e) Assume that the two partition elements always partition so exactly one quarter are to the left, one half in the middle, and one quarter to the right. Write a recurrence for the number of comparisons. Solve this recurrence using constructive induction. Just get the high order term exactly.
(f) Challenge problem, will not be graded. Find the exact high order term for the average number of comparisons.