Quicksort

Quicksort is the most common sorting algorithm in use today.  In light of its technological impact, it's good to know how it works. 

...

Which value to use as the pivot?   Consider this:  on average, for any randomly chosen element in the set (array), the value of that element is the mean of all the values.   Thus, on average, half of the values in the set are smaller than any randomly chosen value and half are thus larger.   What does this all mean?   It means that it doesn't matter which element we choose to be our pivot because on average, half of the values will be larger than our pivot and half will be smaller, which is what we want.    So, why not pick the first element?   It's statistically no different than any other elenent and its real easy to find!

On average, quicksort will be faster than mergesort because the partitioning process of breaking the set into "smaller" and a "larger" subsets is less computationally expensive than mergesort's generalized merge operation.  On the other hand, if the set is pathological, e.g. it's already sorted, Quicksort will degenerate into a O(N^2^) behavior while mergesort will always be O(N*log(N)). 

Here's a very basic implementation of Quicksort in an imperative coding style:

...