Wrapping Up

Benchmarking is a powerful technique that measures code execution speed in a fine-grained way, allowing you to know the true, actual-time difference between competing algorithms. This is especially useful when you want to compare two algorithms that fall within the same category of Big O. However, benchmarking can even reveal surprises about algorithms that aren’t in the same category. As you discovered in this chapter, in some cases, the O(N²) Insertion Sort algorithm can be faster than O(N log N) Mergesort!

On the other hand, you also learned that benchmarking is only useful when used correctly. There are numerous gotchas that can derail your experiments without you even realizing it. Therefore, it’s worthwhile to periodically look back at the gotchas in this chapter to make sure you’re setting up your benchmarking code properly.

In the next chapter, we’ll continue with our analysis of Mergesort vs. Quicksort. And in doing so, we’ll stir things up once again, this time with the concept of randomization algorithms.