Quicksort Explained

The essence of Quicksort is to

• Find the value in the array that we think will be in the middle once the array is sorted (we call this value the pivot).

• Rearrange the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it (which we call “partitioning”).

  After rearranging, a couple of important things are true:

  • The pivot is now in its final sorted position.
  • All elements before the pivot are less than or equal to it, and all elements after the pivot are greater than or equal to it, but those sets aren't necessarily sorted themselves.

• Recursively apply the same process to the subarray of elements before the pivot and the subarray of elements after the pivot.

Quicksort Visualization

Let's explore how Quicksort works with an interactive visualization. You can just dive in and play with it, but we've suggested some particular things to try in the discussion below the applet.

Observing the Basics

Leave the settings at their defaults (size 15, seed 12345, median-of-3 pivot, reverse data) and click Reset to ensure we're starting from the same place. In fact, you can just click the button below when you're ready to start and it'll set everything up for you.

Then click Step repeatedly to see how the algorithm progresses. Some things to notice:

• We've begin with a reverse-sorted array because everything has to move, which makes the divide-and-conquer nature of the algorithm clearer.
• We've picked a good heuristic for choosing the pivot: median-of-three. By looking at three carefully chosen elements, we make a guess as to what the median is likely to be. In this particular case, we guess right every time.
• The pivot element (yellow) raises up to indicate that it's being used to partition the array.
• The other elements slide left or right to make room for the pivot to drop into its final position.
• The pivot turns green and locks when it's in its final position.
• The subarray currently being processed is indicated by the dashed line and label below the array.

You can change the random seed (or click New Array to pick a new random seed) to see different initial arrays, but because the array begins exactly reverse-sorted, the algorithm will behave identically each time.

Rather than click Step repeatedly, you can click Play to have it run automatically. You can pause the simulator at any time, and control the pace with the speed slider. You can also adjust the size of the array (31 is a good size if you want to try a bigger example).

Trying a Randomly Sorted Array

For a first experiment, switch the data to “random” and click New Array, keeping the pivot selection at “median-of-3”. Then click Play to see how it does. You should see that it finishes quite quickly, because the median-of-three heuristic is doing a good job of picking pivots that divide the array roughly in half each time.

It's probably a good idea to click New Array a few times to see how it does on different random arrays.

Trying a Reverse-Sorted Array with a Random Pivot

Now let's try the same experiment with a reverse-sorted array and a random pivot-selection strategy. Switch the data to “reverse” and the pivot selection to “random”, then click Play.

You should see that the performance with these settings is also okay. Sometimes it won't make the best choice, but on average it does a decent job of dividing the array, and so it finishes in a reasonable time.

Trying a Random Array with First-Element Pivot

Now switch the data back to “random” and the pivot selection to “first”, then click Play.

Trying a Reverse-Sorted Array with First-Element Pivot

Now switch the data back to “reverse” and keep the pivot selection at “first”, then click Play.

Quicksort's Worst Case

If we pick the pivot poorly, Quicksort can degrade to quadratic time. This worst-case performance happens when the pivot is always the largest or smallest element in the subarray, which leads to unbalanced partitions. For example, if we always pick the first element as the pivot and the array is already sorted (or reverse-sorted), each partitioning step will only reduce the problem size by one element.

To hit the worst case, we need to consistently pick a terrible pivot. Let's look at how likely picking a bad pivot is with different pivot selection strategies.

• First Element: If the array is already sorted or reverse-sorted, this strategy will always pick the worst pivot. So the worst case is quite easy to trigger (sometimes data is already sorted, or nearly so).
  • Arguably, no one should ever use this strategy. Yet in practice, some implementations do. 😖
• Median-of-Three: This strategy is more robust, but if it uses fixed positions (such as the first, middle, and last elements), an adversary could force it into the worst case by carefully constructing the array so that the median-of-three pick is always a very poor choice.
  • Such an input is very unlikely to occur naturally, but bad actors could deliberately create inputs that exploit this weakness in what is known as an algorithmic complexity attack, where the goal is denial of service by causing the algorithm to run slowly.
• Random: This strategy is the most robust against worst-case scenarios. Because the pivot is chosen randomly, the likelihood of consistently picking a terrible pivot (or, to be fair, a really good one) is extremely low. While it's theoretically possible to hit the worst case with random selection, the probability decreases exponentially with the number of elements.

(When logged in, completion status appears here.)

Previous Page Go to Parent Page