# How does quicksort with 3-way partitioning ~ $(2 ln 2) NH$ become linear time complexity with many duplicated keys?

From Algorithms 4th:

Quicksort with 3-way partitioning uses ~$$(2\ln 2)NH$$ compares to sort $$N$$ items, where $$H$$ is the Shannon entropy, defined from the frequencies of key values.

$$H = -(p_{1}\log_{2}{p_1} + p_{2}\log_{2}{p_2} + .... + p_{k}\log_{2}{p_k})$$

Given $$N$$ keys with $$k$$ distinct key values, for each $$i$$ from $$1$$ to $$k$$ define $$f_{i}$$ to be frequency of occurrence of the $$i$$-th key value and $$p_{i}$$ to be $$f_{i} / N$$, the probability that the $$i$$-th key value is found when a random entry of the array is sampled.

How does $$(2 \ln 2)NH$$ become linear when there are many duplicated keys?

So does it mean that I need to prove:

$$H$$ is a constant (or should I say have a upperbound ?), and not related to $$N$$, when there are many duplicated keys.

Basically yes and slightly no.

The purpose of the quoted paragraphs is to summarize the improvement of quicksort with 3-way partitioning over the basic quicksort (with Hoare partition scheme) in the case of many duplicated keys. The root cause of the improvement is simple, "every item encountered leads to an exchange except for those items with keys equal to the partitioning item’s key". The quantification of the improvement is given by that formula involving the Shannon entropy.

How does $$(2\ln2)NH$$ become linear when there are many duplicated keys? So does it mean that I need to prove: $$H$$ is a constant (or should I say have a upper bound ?), and not related to $$N$$, when there are many duplicated keys.

I would turn the question around.

How can we define "many duplicated keys"? The book Algorithms chooses to mention this concept casually, probably in an attempt to make the situation sounds immediately familiar to the widest audience at the expense of some rigor.

In fact, the more applicable and rigorous concept should be "stable discrete distributions", i.e., the distribution of all discrete key values stays roughly the same, which is somewhat more technical but still within reach of most of targeted audience of that book. Note that entropy of a multi-set is determined by the frequencies of all values appearing in the multi-set, as explained in the last paragraph quoted in the question. If the distribution of all key values stays the same, the entropy of a sample array viewed as a multi-set will be roughly the same regardless of the sample size. When sample size goes larger and larger, there will be more and more duplicate keys in the sense of the sum of duplicities. For example, if the probability of some key $$k$$ is 0.2, then there is likely about 20 items with key $$k$$ when the sample size is 100 and there is likely about 200 items with key $$k$$ when the sample size is 1000. That is the meaning of "many duplicate keys" here.

In other words, we could simply define "many duplicated keys" by "the same entropy regardless of the size $$N$$". Then there is, actually, nothing for you to prove once you have agreed that "Quicksort with 3-way partitioning uses $$\sim(2\ln2)NH$$".

Or, we could try to prove the following more precise proposition.

It will take quicksort with 3-way partitioning approximately $$(2\ln2)NH$$ time on average to sort an array of size $$N$$ that comes from sampling a discrete distribution with entropy $$H$$, where $$H$$ is a constant and $$N$$ goes to infinity.

The following excerpt of the book implies the explanation above implicitly. The boldface is added by me.

As with standard quicksort, the running time tends to the average as the array size grows, and large deviations from the average are extremely unlikely, so that you can depend on 3-way quicksort’s running time to be proportional to N times the entropy of the distribution of input key values. This property of the algorithm is important in practice because it reduces the time of the sort from linearithmic to linear for arrays with large numbers of duplicate keys. The order of the keys is immaterial, because the algorithm shuffles them to protect against the worst case. The distribution of keys defines the entropy and no compare-based algorithm can use fewer compares than defined by the entropy. This ability to adapt to duplicates in the input makes 3-way quicksort the algorithm of choice for a library sort—clients that sort arrays containing large numbers of duplicate keys are not unusual.

My explanation above suffers the same weakness of ambiguity as the book, although on a slightly different level, since I would also like my explanation to be understood by widest audience easily with least amount of expense of rigor. Hopefully, I have made the point clearly enough so that readers should be comfortable enough to believe he/she has understood the relevant idea in the book.

Assume the Proposition N of the book, which is the first paragraph of this question.

Exercise. Given a constant positive integer $$m$$, it will take quicksort with 3-way partitioning approximately less than $$2N\ln2\log_2m$$ time to sort an array of size $$N$$ whose number of distinct elements is $$m$$. (Hint, maximum entropy with $$m$$ possible values is obtained with uniform distribution.)

• Nice explanation on "many duplicated values". If I understand correctly, it means that as long as there is no key's probability equals 1/N, then complexity is linear. Now I am thinking how to prove your new proposition : " a discrete distribution with finite entropy H, where H is a constant and N goes to infinity. " – Rick Jan 11 at 3:55
• "(many) duplicated keys" == all keys probability not the same, if I understand your answer correctly. – Rick Jan 11 at 4:19
• I added an exercise. It might help your understanding if you try to understand the exercise. – Apass.Jack Jan 11 at 4:46