Is there a sorting algorithm of order $n + k \log{k}$?

Question

I'm given an integer vector which is said to contain many duplicate values (total of k distinct integers), for example

[1, 4, 2, 5, 5, 3, 4, 2, 2, 5]
(n = 10, k = 5)

and am asked to find a sorting algorithm that averages $O(n + k\log{k})$. I've concluded that partial quicksort (or quickselsort) might achieve this, but doesn't seem to utilise that the vector contains duplicates. Am i missing some basic algorithms here?

Answer 1

Here is an approach:

1. Create a hash map (dictionary in python) with keys being the elements of the vector and the corresponding values being the number of times the the element occurs in the vector, i.e. its frequency. Time complexity for this would be $O(n)$ (How? Try to find out and let me know in the comments).
2. Sort all the keys of the map. Time complexity $= O(k\log (k))$ as there are $k$ distinct elements.
3. In a new vector, push each sorted values as many times as its frequency. Look up on a map takes constant time. So this operation would take linear time.

Total complexity would be of $O(n + k\log(k))$

Answer 2

The short answer is no, in the worst-case comparison based algorithms, for reasons stated here.

Using a counting technique will at least take $O(n \log n)$ worst case and $O(n \log k)$ if you use a BST. Here I'll give a variant of quick-sort which also achieves $O(n \log k)$ With a slight modification and a more careful analysis of quick-sort. We will change the "pivot" of quick-sort to never put duplicate elements in separate sub-problem. The partition procedure is as follows:

partition(list A of size n):
  x = SELECT(A, n/2)

  left = list of all elements less than x
  right = list of all elements greater than x
  center = list of all elements equal to x

  return (left, center, right)

Then the overall quick-sort looks like this:

quick-sort(list A of size n):
  if all elements in A are the same:
    return A
  left, center, right = partition(A)
  quick-sort(left)
  quick-sort(right)
  return concat(left, center, right)

The important thing here is the base case, when we only have one unique element in the list, just return the list. This will ensure that we have exactly $k$ leaf nodes in our recursion tree. The recurrence at face-value is:

$$T(n) \leq \max_{i,j} \{T(n - i) + T(n - i - j)\} + O(n)$$

Obviously with some constraints on $i$ and $j$, but that's the idea. Another thing to note is that via SELECT we ensure that center contains all the median elements, this would imply that we only recurse on two sub problems of size less than $n/2$, leading us to:

$$T(n) \leq \max_{l,r} \{T(\tfrac{n}{2} - l) + T(\tfrac{n}{2} - r)\} + O(n)$$

Where $l$ would be the overlap of the median on the left side and $r$ would be overlap of median on the right side. Note that $r + l$ is the number of elements equal to the median. With this we see a clear upper bound of $O(n \log n)$. However, when we include the base cases this becomes better. If we assume that each unique element is repeated $c = n/k = n^*/k$ times (distributed evenly) then we can get the recurrence:

$$T(n) \leq \begin{cases} 1 & n \leq n^*/k\\ T(\tfrac{n}{2} - n^*/2k) + T(\tfrac{n}{2} - n^*/2k) + O(n) & \text{otherwise} \end{cases}$$

If we do recursion tree analysis on this we can see it is $O(n \log k)$.

We could also take advantage of the fact that we do not do $n$ work at each level of recurrence, but rather at level 0 we do $O(n)$, at level 1 we do $O(n - n/k)$, at level 2 we do $O(n - 3n/k)$, at level 3 we do $O(n - 7n/k)$ and so on. Without out our assumption the analysis becomes more tricky, and we would need to do average case analysis. However, I would claim that this assumption is worst case. Intuitively if this assumption did not hold, then we have fewer repetitions for some element $x_i$, but more repetitions for some element $x_j$. Thus, making $x_j$ more likely to be in one of the center's without going too deep in the recursion tree. This would reduce the amount of work on the remaining subproblem(s) more by removing more than $n/k$ elements from the list.