Sorting Quickly

Merge sort and heap sort both run in O(nlgn), which is where the lower limit lies in comparison sort algorithms.

Merge sort is intuitive and fairly straightforward. Heap sort has the advantage of being able to be used in priority queues efficiently.

Then there is quick sort. Quick sort also runs in O(nlgn), but only for its average and best case scenarios. In the worst case, quick sort runs in O(n^2). However, quick sort is preferred over merge sort and heap sort. Why? Because other than the worst case, quick sort runs faster in practice due to its tighter loops. But what about the worst case? The good news is that there is only 1 worst case sequence, which is if at each iteration, we choose the largest number as the pivot. If we use a randomized algorithm of quick sort, the chances of hitting the worst case is 1/n!, which is very low. Hence, in practice, it's worth the risk of hitting the worst case.

Here's my code for quick sort and a test file.
https://gist.github.com/wmwong/6758508#file-quicksort-rb
https://gist.github.com/wmwong/6758508#file-quicksort_test-rb