Chapter 3
How Random Is That?

In the previous two chapters, we encountered a notable trade-off between Mergesort and Quicksort. On the one hand, Quicksort is the faster algorithm in average-case scenarios. On the other hand, Mergesort guarantees speedy sorting in all scenarios, while Quicksort slows down for arrays that already happen to be sorted. The trade-off is this: would you rather use an algorithm that is super fast in most scenarios but sometimes slow or an algorithm that is only moderately fast but guarantees that it’ll never be slow?

In this chapter, you’ll discover that this is a false dichotomy. We can use a technique called randomization to perform Quicksort so that it’s faster than Mergesort in all scenarios. You’ll likewise learn how randomization can play an important role in optimizing data structures and algorithms by greatly improving an algorithm’s speed. And perhaps most fun of all, you’ll get insight into how a computer performs randomization in the first place, from generating random numbers to shuffling arrays.