The Efficiency of Quicksort

To figure out the efficiency of Quicksort, let’s first determine the efficiency of a single partition.

When we break down the steps of a partition, we’ll note that a partition involves two primary types of steps:

• Comparisons: We compare each of the values at hand to the pivot.
• Swaps: When appropriate, we swap the values being pointed to by the left and right pointers.

Each partition has at least N comparisons—that is, we compare each element of the array with the pivot. This is true because a partition always has the left and right pointers move through each cell until the left and right pointers reach each other.

The number of swaps, however, will depend upon how the data is sorted. A single partition can have, at most, N / 2 swaps, as even if we’d swap values at every opportunity, each swap takes care of two values. As you can see in the following diagram, we partition six elements in just three swaps:

Now, in most cases, we’re not making a swap every step of the way. For randomly sorted data, we generally swap about half of the values. On average, then, we’re making about N / 4 swaps.

So on average, we make about N comparisons and N / 4 swaps. We can say, then, that there are about 1.25N steps for N data elements. In Big O notation, we ignore constants, so we’d say that a partition runs in O(N) time.

Now, that’s the efficiency of a single partition. But Quicksort involves many partitions, so we need to conduct further analysis to determine the efficiency of Quicksort.

Quicksort from a Bird’s-Eye View

To visualize this more easily, see the , depicting a typical Quicksort on an array of eight elements from a bird’s-eye view. In particular, the diagram shows how many elements each partition acts upon. We’ve left out the actual numbers from the array since the exact values don’t matter. Note that in the diagram, the active subarray is the group of cells that’s not grayed out.

We can see that we have eight partitions, but each partition takes place on subarrays of various sizes. We perform a partition on the original array of eight elements but also perform partitions on subarrays of sizes 4, 3, and 2, and another four partitions on arrays of size 1.

Since Quicksort is essentially comprised of this series of partitions, and each partition takes about N steps for N elements of each subarray, if we add the sizes of all the subarrays together, we’ll get the total number of steps Quicksort takes:

We see that where the original array has 8 elements, Quicksort takes about 21 steps. This assumes a best- or average-case scenario, where the pivot ends up roughly in the middle of the subarray after each partition.

For an array of 16 elements, Quicksort takes about 64 steps, and for an array of 32 elements, Quicksort takes about 160 steps. Take a look at this table:

(While in our example earlier, the number of Quicksort steps for an array of size 8 was 21, I put 24 in this table. The exact number can vary from case to case, and 24 is also a reasonable approximation. I specifically made it 24 to make the following explanation a little clearer.)

The Big O of Quicksort

How do we categorize Quicksort in terms of Big O notation?

If we look at the pattern shown earlier, we’ll note that the number of Quicksort steps for N elements in the array is about N multiplied by log N, as shown in the following table:

In fact, this is exactly how to express the efficiency of Quicksort. It’s an algorithm of O(N log N). We’ve discovered a new category of Big O!

The shows how O(N log N) looks beside other categories of Big O.

Now, it’s not a coincidence that the number of steps in Quicksort just happens to align with N * log N. If we think about Quicksort more broadly, we can see why it’s this way.

Each time we partition the array, we end up breaking it down into two subarrays. Assuming the pivot ends up somewhere in the middle of the array—which is what happens in the average case—these two subarrays are of roughly equal sizes.

How many times can we break an array into halves until we’ve broken it completely down to the point where each subarray is of size 1? For an array of size N, this will take us log N times. Take a look at the following diagram:

As you can see, for an array of size 8, it takes us three halvings until we’ve reduced the array into eight individual elements. This is log N, and fits with our definition of log N as being the number of times it takes to halve something until we reach 1.

So this is why Quicksort takes N * log N steps. We have log N halvings, and for each halving, we perform a partition on all the subarrays whose elements add up to N. (They add up to N because all the subarrays are simply pieces of the original array of N elements.)

This is illustrated in the previous diagram. At the top of the diagram, for example, we partition the original array of eight elements, creating two subarrays of size 4. We then partition both subarrays of size 4, which means that we’re again partitioning eight elements.

Bear in mind that O(N * log N) is just an approximation. In reality, we first perform an extra O(N) partition on the original array as well. Additionally, an array doesn’t cleanly break into two even halves, since the pivot is not part of the halving.

Here’s what a more realistic example looks like, where we ignore the pivot after each partition: