If there is anyone who is familiar with Quicksort try to help me to understand the following. I am taking specifically some text from the book 'The Concrete Tetrahedron' Manuel Kauers . Peter Paule though of course Quicksort is described in many articles and texts. Let $c_n$ be the average number of comparisons needed to sort n elements. On p.4 of that text he has $c_3=\frac{8}{3}$ which he explains by the pivot may be the minimum, the middle element or the maximum. Two comparisons are needed to determine this. If it is the minimum or the maximum, then the other two numbers are on the same side and it requires $c_2=1$ comparisons to sort them. If the pivot is the middle element, then there is one number to its left and one number to its right and no further comparison is needed. Assuming that each case is equally likely, we expect $2+\frac{(1+0+1)}{3}$ comparisons on average.
First how does he get this for $n=3$ ? And specifically when expanded each of the $4$ terms ? And what exactly is the pivot in general or is the pivot just taken as any random choice? Next he goes on to say:
In the general case, when we are sorting n numbers and choose a pivot p, that pivot can be the $k$-th smallest element of the list for any $k=1, ... ,n$. In every case, we need $n-1$ comparisons to bring the $k-1$ smaller elements to its left and the $n-k$ greater elements to the right. Then we need $c_{k-1}$ comparisons on average to sort the left part and $c_{n-k}$ comparisons on average to sort the right part, thus $n-1+c_{k-1}+c_{k-1}$ comparisons in total. Taking the average over all possible choices for $k$, we find
$$c_n=\frac 1 n \sum_{k=1}^n(n-1+c_{k-1}+c_{n-k})= (n-1)+\frac 1 n \sum_{k=1}^n(c_{k-1}+c_{n-k})$$
Next how does he get this and again why is there not more comparisons needed to find this 'pivot' which to me the term 'pivot' is rather ambiguous itself. Is it chosen randomly ?