Randomized Quicksort

Since the runtime of Quicksort can be slow ($\theta (n^2)$) if the array is already sorted or nearly sorted, we want to randomize the pivot element.

Runtime

Average $O(n\ast lg(n))$

How does it work?

The function is identical to Quicksort, but the difference is that we now use the function Randomized Partition.