Randomized Quicksort

Consider a randomized version of Quick Sort:

  Algorithm RandQS

  Input: A set of numbers S.

  Output: The elements of S 
          in increasing order.

  1. Choose an element y uniformly 
     at random from S.

  2. By comparing each element of S with
     y, determine S1 of elements smaller
     than y, and S2 of elements larger 
     than y.

  3. Recursively sort S1 and S2. Output
     the sorted S1, followed by y, and
     then the sorted S2.

We proved that the expected running time of RandQS is O(nlogn) and that this holds for every input.