Quick sort worst case complexity improvement
The simplest way is to choose the median as pivot. Since the median can be found in linear time, the overall algorithm would satisfy the recurrence
$$ T(n) = T(\lfloor \tfrac{n-1}{2} \rfloor) + T(\lceil \tfrac{n-1}{2} \rceil) + O(n), $$
whose solution is $T(n) = O(n\log n)$.