Quicksort in Python

I am reading Programming Pearls and figure it would be fun to write Quicksort in Python.

Here are my code and benchmarks.

When I try to compare my code with others, I am surprised to see many faulty implementations of Quicksort with quadratic runtime on certain input.

The key to write a correct and fast Quicksort:

1. Watch out for list of equal items. qsort2 uses 2 pointers (i, j) to make sure the problem is divided into subproblems of similar size.
2. Watch out for sorted list. qsort3 uses randomization and qsort_mo3 uses median-of-3 to pick a good pivot in order to avoid quadratic runtime.