The Efficiency of Quicksort

To figure out the efficiency of Quicksort, let’s first determine the efficiency of a partition. When breaking down the steps of a partition, we’ll note that a partition consists of two types of steps:

• Comparisons: We compare each value 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 depends on how the data is sorted. Each partition has at least one swap, and the most swaps that a partition can have would be N / 2, since even if we’d swap every possible value, we’d still be swapping the ones from the left half with the ones from the right half. See this diagram:

Now, for randomly sorted data, there would be roughly half of N / 2 swaps, or N / 4 swaps. So with N comparisons and N / 4, we’d say there are about 1.25N steps. In Big O Notation, we ignore constants, so we’d say that a partition runs in O(N) time.

So that’s the efficiency of a single partition. But Quicksort involves many partitions on arrays and subarrays of different sizes, so we need to do a further analysis to determine the efficiency of Quicksort.

To visualize this more easily, here is a diagram 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 numbers don’t matter. Note that in the diagram, the active subarray is the group of cells that are not grayed out.

We can see that we have eight partitions, but each partition takes place on subarrays of various sizes. Now, where a subarray is just one element, that’s our base case, and we don’t perform any swaps or comparisons, so the significant partitions are the ones that take place on subarrays of two elements or more.

Since this example represents an average case, let’s assume that each partition takes approximately 1.25N steps. So that gives us:

If we do this analysis for arrays of various sizes, we’ll see that for N elements, there are about N * log N steps. To get a feel for N * log N, see the following table:

In the preceding example, for an array of size 8, Quicksort took about 21 steps, which is about what 8 * log 8 is (24). This is the first time we’re encountering such an algorithm, and in Big O, it’s expressed as O(N log N).

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 is this way:

When we begin Quicksort, we partition the entire array. Assuming that the pivot ends up somewhere in the middle of the array—which is what happens in the average case—we then break up the two halves of the array and partition each half. We then take each of those halves, break them up into quarters, and then partition each quarter. And so on and so forth.

In essence, we keep on breaking down each subarray into halves until we reach subarrays with elements of 1. How many times can we break up an array in this way? For an array of N, we can break it down log N times. That is, an array of 8 can be broken in half three times until we reach elements of 1. You’re already familiar with this concept from binary search.

Now, for each round in which we break down each subarray into two halves, we then partition all the elements from the original array over again. See this diagram:

Since we can break up the original array into equal subarrays log N times, and for each time we break them up, we must run partitions on all N cells from the original array, we end up with about N * log N steps.

For many other algorithms we’ve encountered, the best case was one where the array was already sorted. When it comes to Quicksort, however, the best-case scenario is one in which the pivot always ends up smack in the middle of the subarray after the partition.