Quicksort Q: Finitely many distinct keys

Question

Need to show that a quicksort with a special partitioning, where an array gets partitioned into 3 parts (< than 3 pivot, = to pivot, > than pivot) and a special array of size N where only 7 distinct keys are possible can be sorted in O(N).

So, I suppose we can assume the pivot is being chosen somewhere in the middle (otherwise we could have something like [0, 1, 2, 3, 4, 5, 6, 6, 6, 6, .....] and that should take O(N^2)).

Here is what I am thinking:
Suppose we did the first partitioning. Now we move to the recursive step 2. Suppose we only focus on the right partition. Since every element here is greater than the pivot, and there were only 7 distinct keys, the number of distinct keys in this partition is strictly less than 7. This implies that after 7 iterations of the algorithm, all elements in the left and right sub-sub-...-partitions should be the same.

Now, I can see how this would be O(N) if the algorithms stopped recurring on a constant array, but my understanding is that it doesn't. Please clarify this if its not the case.

So what's going on here?

Answer 1

The quicksort algorithm looks like this:

quicksort(A, lo, hi):
  if lo < hi:
    p := partition(A, lo, hi)
    quicksort(A, lo, p - 1)
    quicksort(A, p + 1, hi)

We have a special partition that is 3-way, so let's say it returns the equal range for whatever pivot it picks and we just need to go below and above that:

quicksort(A, lo, hi):
  if lo < hi:
    p1, p2 := 3-way-partition(A, lo, hi)
    quicksort(A, lo, p1 - 1) // (1)
    quicksort(A, p2 + 1, hi) // (2)

Now, consider the very worst case. We have an array that looks like [0,1,2,3,4,5,6,6,6,6...] and our pivot selection algorithm is as dumb as possible: it picks the pivots in strictly increasing order. In this case, the first recursive call ((1) above) will always do nothing because there will be nothing smaller than the pivot. So we're only ever dealing with one single recursive call - of size N - 1.

Each recursive call reduces the problem size by one, until the 7th recursive call (which will pick the 6 pivot) - that one completes the sort. This is the key step in only having 7 distinct keys - you only need at most 7 calls. Each of those 7 calls iterates the entire array... that's O(7N) == O(N). More generally, if there are only k distinct keys, you can say that the worst case is O(kN) from the same argument.