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:
- Watch out for list of equal items.
qsort2uses 2 pointers (i, j) to make sure the problem is divided into subproblems of similar size.
- Watch out for sorted list.
qsort3uses randomization and
qsort_mo3uses median-of-3 to pick a good pivot in order to avoid quadratic runtime.