Heap and Heapsort in Python

Another exercise from Programming Pearls: Heap. I finished the code a week ago but didn’t have the time for the blog post until now. Here’s the code:

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: 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.

Writing a Binary Search

Background As I am preparing for interviews recently, this is a good time to write about my experience in writing a binary search. Please correct me if I get anything wrong in the content. Binary Search Binary search is always one of the most popular algorithms and at the same time tough to implement correctly. It is surprisingly hard to find a correct while easy-to-modify binary search code out there.