Below is an implementation of the recursive quick sort algorithm. The quickSort operation utilizes two helper operations $($partition and join$)$ both of which have asymptotic performance of $(N),$ where $N=|q|.$

One of the jobs of partition is to pick a pivot item from the incoming $q.$ It uses this pivot when removing the remaining items from the incoming $q$ and putting them into either $q1$ or $q2($see ensures clause for how partition chooses $q1$ or $q2$ based on the pivot $).$

To do:

Determine a recurrence equation for quickSort for the case where partition always chooses a pivot so that the length of $|)/(2_{{?}_{?}}|$ and $|)/(2|$

Determine a recurrence equation for quickSort for the case where partition always chooses a pivot so that either: