The Efficiency of the Fisher-Yates Shuffle

Let’s analyze the efficiency of the Fisher-Yates Shuffle. The steps of this algorithm consist of generating random numbers and performing swaps. For each of the N values in the array (besides the last one), we generate a random number and then perform a swap. All in all, this is N-1 number generations, and N-1 swaps, yielding 2N-2 steps, which boils down to O(N). This is way faster than any known sorting algorithm, and kind of makes sense since it’s a lot easier to make chaos out of order than it is to make order out of chaos.

In terms of space, the Fisher-Yates Shuffle jumbles all the values in place and doesn’t consume any extra memory.

Now that we’ve determined that shuffling takes O(N) time, we understand why shuffling an array before Quicksort is worth our while. As we’ve seen, if we suspect that we’re dealing with a sorted array, Quicksort will have a speed of O(N²). But if we spend O(N) time preshuffling the array, we can reduce Quicksort’s time to O(N log N), which makes preshuffling a potentially great move. That is, even with preshuffling, Quicksort’s total time is still, from a Big O notation standpoint, O(N log N). This is because we have:

which yields (N log N) + N, which is still O(N log N) since we drop the lower factor of “+ N”.

So, preshuffling the array doesn’t slow Quicksort down at all from a Big O perspective.