While the version of quicksort that we implemented is almost always able to perform at speeds of O(n*log(n)), its Big O is still technically O(n^2) due to the worst-case scenario. We can fix this by altering the algorithm slightly.
Two of the approaches are:
O(n) time.O(1) time.The random approach is easier to code, which is nice if you're the one writing the code.
The function simply shuffles the list into random order before sorting it, which is an O(n) operation. The likelihood of shuffling a large list into sorted order is so low that it's not worth considering.
Another popular solution is to use the "median of three" approach. Three elements (for example: the first, middle, and last elements) of each partition are chosen and the median is found between them. That item is then used as the pivot.
This approach has less overhead, and also doesn't require randomness to be injected into the function, meaning it can remain deterministic and pure.