Intuitive explanation for why QuickSort is n log n?

Question

Is anybody able to give a 'plain english' intuitive, yet formal, explanation of what makes QuickSort n log n? From my understanding it has to make a pass over n items, and it does this log n times...Im not sure how to put it into words why it does this log n times.

score 176 · Answer 1 · edited Dec 24 '20 at 03:04

Complexity

A Quicksort starts by partitioning the input into two chunks: it chooses a "pivot" value, and partitions the input into those less than the pivot value and those larger than the pivot value (and, of course, any equal to the pivot value have go into one or the other, of course, but for a basic description, it doesn't matter a lot which those end up in).

Since the input (by definition) isn't sorted, to partition it like that, it has to look at every item in the input, so that's an O(N) operation. After it's partitioned the input the first time, it recursively sorts each of those "chunks". Each of those recursive calls looks at every one of its inputs, so between the two calls it ends up visiting every input value (again). So, at the first "level" of partitioning, we have one call that looks at every input item. At the second level, we have two partitioning steps, but between the two, they (again) look at every input item. Each successive level has more individual partitioning steps, but in total the calls at each level look at all the input items.

It continues partitioning the input into smaller and smaller pieces until it reaches some lower limit on the size of a partition. The smallest that could possibly be would be a single item in each partition.

Ideal Case

In the ideal case we hope each partitioning step breaks the input in half. The "halves" probably won't be precisely equal, but if we choose the pivot well, they should be pretty close. To keep the math simple, let's assume perfect partitioning, so we get exact halves every time.

In this case, the number of times we can break it in half will be the base-2 logarithm of the number of inputs. For example, given 128 inputs, we get partition sizes of 64, 32, 16, 8, 4, 2, and 1. That's 7 levels of partitioning (and yes log₂(128) = 7).

So, we have log(N) partitioning "levels", and each level has to visit all N inputs. So, log(N) levels times N operations per level gives us O(N log N) overall complexity.

Worst Case

Now let's revisit that assumption that each partitioning level will "break" the input precisely in half. Depending on how good a choice of partitioning element we make, we might not get precisely equal halves. So what's the worst that could happen? The worst case is a pivot that's actually the smallest or largest element in the input. In this case, we do an O(N) partitioning level, but instead of getting two halves of equal size, we've ended up with one partition of one element, and one partition of N-1 elements. If that happens for every level of partitioning, we obviously end up doing O(N) partitioning levels before even partition is down to one element.

This gives the technically correct big-O complexity for Quicksort (big-O officially refers to the upper bound on complexity). Since we have O(N) levels of partitioning, and each level requires O(N) steps, we end up with O(N * N) (i.e., O(N²)) complexity.

Practical implementations

As a practical matter, a real implementation will typically stop partitioning before it actually reaches partitions of a single element. In a typical case, when a partition contains, say, 10 elements or fewer, you'll stop partitioning and and use something like an insertion sort (since it's typically faster for a small number of elements).

Modified Algorithms

More recently other modifications to Quicksort have been invented (e.g., Introsort, PDQ Sort) which prevent that O(N²) worst case. Introsort does so by keeping track of the current partitioning "level", and when/if it goes too deep, it'll switch to a heap sort, which is slower than Quicksort for typical inputs, but guarantees O(N log N) complexity for any inputs.

PDQ sort adds another twist to that: since Heap sort is slower, it tries to avoid switching to heap sort if possible To to that, if it looks like it's getting poor pivot values, it'll randomly shuffle some of the inputs before choosing a pivot. Then, if (and only if) that fails to produce sufficiently better pivot values, it'll switch to using a Heap sort instead.

Thank you for this. The accepted answer here merely restated what the OP (and I) already knew (n operations done log n times), but glossed over the only important part: why is it done log n times? This answer is a nice and simple explanation of where the log term actually comes from. — Cam Jackson, Dec 13 '13 at 00:17
Is this really correct? Each partition operation creates 2 new groups, which means that after your first partition you'll end up with 2 calls to Partition(), each partition being 64 elements in size, this will generate 4 calls with groups of 32, and then 8 calls with groups of 16 and so on. In total, the number of calls to Partition() should be around 254, not 7. — Raikol Amaro, Jun 25 '19 at 18:21
@RaikolAmaro: the calls have a *depth* of 7. If you add up all the calls at a given depth, together they operate on all N elements. (2 * 128 at the first level, 4*64 at the second, and so on). So, you get calls to a depth of log(N), and at each level the total number of operations is proportional to N. — Jerry Coffin, Jun 25 '19 at 18:42
The iteration stack has a depth of 7, yes, but in your answer you say that: "you divide into groups of 64, 32, 16, 8, 4, 2, 1 items -- 7 iterations" and then: "Each of those iterations scans through the entire array to partition it". both statements are incorrect because there's NOT 7 iterations and each iteration does NOT scan through the entire array, instead, each iteration scans through progressively smaller array sizes. — Raikol Amaro, Jun 25 '19 at 18:58
@RaikolAmaro: Sorry, but you're simply reading it incorrectly. The "iterations" isn't referring to the number of iterations through the loop inside a single call to "partition", but to the depth of calls. — Jerry Coffin, Jun 25 '19 at 19:04
@JerryCoffin, I see what you mean now, but I do believe there's some ambiguity in the way you've explained it in your original answer. Thanks for the answer anyway. — Raikol Amaro, Jun 25 '19 at 20:14
@RaikolAmaro: yeah, it probably wasn't completely clear. I've rewritten it to be somewhat more explicit. — Jerry Coffin, Jun 26 '19 at 17:50
If the "ideal" case is n log n, why is it big-O and not theta? That is, under what input conditions can it run faster than n log n? I feel the correct and only characterization is O(n^2). — Russ, Jun 03 '20 at 15:51
@Russ: as I said, O(N^2) is technically correct. But, most people use big-O notation exclusively, and ignore (or haven't even heard of) big-theta. From a formal viewpoint, you're right. From an informal viewpoint, they're at least correct that it's worthwhile to realize that in practical use there's a substantial difference between quicksort on the one hand, and insertion sort, bubble sort or selection sort on the other. The fact that they're all O(N^2) loses a lot of important information (and adding big-theta doesn't really recover much either). — Jerry Coffin, Jun 03 '20 at 16:49
In particular, one common variant of bubble sort is THETA(N), so if we see O(N^2) for both, and THETA(N) for one and THETA(N log N) for the other, the bubble sort variant would *look* like the better choice. In reality, it's faster only in the degenerate case of sorting already-sorted data, and almost always drastically slower. — Jerry Coffin, Jun 03 '20 at 16:53

score 49 · Accepted Answer · answered May 03 '12 at 05:24

49

Each partitioning operation takes O(n) operations (one pass on the array). In average, each partitioning divides the array to two parts (which sums up to log n operations). In total we have O(n * log n) operations.

I.e. in average log n partitioning operations and each partitioning takes O(n) operations.

answered May 03 '12 at 05:24

Eugene Retunsky

13,009
4
52
55

28

To the people who are reading this answer, SCROLL DOWN for a better answer. – c0degeas Jun 13 '19 at 04:50
There's an issue I see with this intuition. Consider the following (bad) quicksort variation: at each point in time, we select either the maximum or minimum element of the array and use it as the pivot, and we do so with equal probability. On average, the subarray of smaller elements will have size (n - 1)/2, as with the subarray of the larger elements. And yet, this algorithm will always take time Omega(n^2) to complete. So the fact that on average each split is on average 50/50 doesn't necessarily mean that the algorithm is going to be fast. There's more to the story than that. – templatetypedef Jun 26 '19 at 17:59

templatetypedef · Answer 3 · 2022-05-25T04:45:37.107

There's a key intuition behind logarithms:

The number of times you can divide a number n by a constant before reaching 1 is O(log n).

In other words, if you see a runtime that has an O(log n) term, there's a good chance that you'll find something that repeatedly shrinks by a constant factor.

In quicksort, what's shrinking by a constant factor is the size of the largest recursive call at each level. Quicksort works by picking a pivot, splitting the array into two subarrays of elements smaller than the pivot and elements bigger than the pivot, then recursively sorting each subarray.

If you pick the pivot randomly, then there's a 50% chance that the chosen pivot will be in the middle 50% of the elements, which means that there's a 50% chance that the larger of the two subarrays will be at most 75% the size of the original. (Do you see why?)

Therefore, a good intuition for why quicksort runs in time O(n log n) is the following: each layer in the recursion tree does O(n) work, and since each recursive call has a good chance of reducing the size of the array by at least 25%, we'd expect there to be O(log n) layers before you run out of elements to throw away out of the array.

This assumes, of course, that you're choosing pivots randomly. Many implementations of quicksort use heuristics to try to get a nice pivot without too much work, and those implementations can, unfortunately, lead to poor overall runtimes in the worst case. @Jerry Coffin's excellent answer to this question talks about some variations on quicksort that guarantee O(n log n) worst-case behavior by switching which sorting algorithms are used, and that's a great place to look for more information about this.

score 2 · Answer 4 · answered May 03 '12 at 05:28

2

Well, it's not always n(log n). It is the performance time when the pivot chosen is approximately in the middle. In worst case if you choose the smallest or the largest element as the pivot then the time will be O(n^2).

To visualize 'n log n', you can assume the pivot to be element closest to the average of all the elements in the array to be sorted. This would partition the array into 2 parts of roughly same length. On both of these you apply the quicksort procedure.

As in each step you go on halving the length of the array, you will do this for log n(base 2) times till you reach length = 1 i.e a sorted array of 1 element.

answered May 03 '12 at 05:28

Siddharth Gaur

111
1
11

You're right, but don't mix average and median. Median is what allows you to divide into two parts with same length (+-1). – kvetis Apr 21 '17 at 11:09
Average won't give middle element. Median will give middle element/s. Answer needs fixing for this part. Otherwise good. – Manohar Reddy Poreddy Apr 18 '18 at 06:53
Since the list may be unsorted to start, and you wish to scan once for the pivot, the best I can think to do is average the numbers and pick the pivot as the closest to that. Now where we go wrong is inputs like 1 1 1 1 1 1 1 2 864. The pivot is 2, leading to imbalance. – Russ Jun 03 '20 at 15:48

score 1 · Answer 5 · answered Aug 11 '19 at 14:33

Break the sorting algorithm in two parts. First is the partitioning and second recursive call. Complexity of partioning is O(N) and complexity of recursive call for ideal case is O(logN). For example, if you have 4 inputs then there will be 2(log4) recursive call. Multiplying both you get O(NlogN). It is a very basic explanation.

score 0 · Answer 6 · answered Feb 21 '16 at 05:27

0

In-fact you need to find the position of all the N elements(pivot),but the maximum number of comparisons is logN for each element (the first is N,second pivot N/2,3rd N/4..assuming pivot is the median element)

answered Feb 21 '16 at 05:27

Prdp

11

This is not true. For starters, notice that N + N / 2 + N / 4 + N / 8 + ... = N(1 + 1/2 + 1/4 + 1/8 + ...) <= 2N, which would give a bound that beats the sorting barrier. Second, as a counterexample, suppose you pick the largest element as the pivot in both the first and second steps. Then placing the second pivot takes N - 1 comparisons, not N / 2. – templatetypedef Jun 26 '19 at 18:02

score 0 · Answer 7 · answered Jan 10 '23 at 13:43

In the case of the ideal scenario, the first level call, places 1 element in its proper position. there are 2 calls at the second level taking O(n) time combined but it puts 2 elements in their proper position. in the same way. there will be 4 calls at the 3rd level which would take O(n) combined time but will place 4 elements into their proper position. so the depth of the recursive tree will be log(n) and at each depth, O(n) time is needed for all recursive calls. So time complexity is O(nlogn).