Suppose function inplace_quick_sort is executed on a sequence with duplicate elements. Prove that the algorithm still correctly sorts the input sequence. What happens in the partition step when there...

Suppose function inplace_quick_sort is executed on a sequence with duplicate

elements. Prove that the algorithm still correctly sorts the input

sequence. What happens in the partition step when there are elements

equal to the pivot? What is the running time of the algorithm if all the

input elements are equal?

If the outermost while loop of our implementation of _inplace_quick_sort

(line 7 of Code Fragment 12.6) were changed to use condition left

(rather than left <=>

give a specific input sequence on which such an implementation fails.