# Efficent deterministic algorithm to sort n numbers with many duplicates ( distinct integers $O(\log n)$)

I seek to sort a sequence S of n integers with many duplications, such that the number of distinct integers in S is $$O(\log n)$$. Give an $$O(n \log \log n)$$ worst-case time algorithm to sort such sequences. I tried quick-sort, Merge-sort, selection-sort but not getting the required running time. So the question is to design a deterministic algorithm for the problem described.

It is from the book Algorithm Design Manual by Steven Skiena (2nd Ed) problem no 4-23, page no- 154 with some modification.

• Hint: The problem with Hoare's original quicksort is that it doesn't handle ranges of equal keys the way you'd hope. How could you fix that? – Pseudonym Jan 24 '17 at 6:31
• @ Pseudonym I am not able to understand what do you mean by "ranges of equal keys" . Did you mean when all keys are same ? I know there is a Randomized quick-sort but I am looking deterministic algorithm. – user35837 Jan 24 '17 at 11:42
• I mean when there are a significant number of equal keys. When the entropy of the key distribution is $o(\log n)$. – Pseudonym Jan 24 '17 at 12:29

How much time does it take to make $$\Theta(n)$$ queries in a Red-Black Tree with size $$O(\log n)$$ ?

A detailed solution follows:

Let $$T$$ be a new empty self-balancing search tree storing pairs of integers, where the order property is w.r.t. the first element of each pair. For each element $$A[i]$$ of the original array, query $$T$$ for a node which first element is $$A[i]$$. If there is no such node, insert a new node $$(A[i], 1)$$; otherwise, update the node $$(A[i], m)$$ with $$(A[i], m+1)$$.

After you are done with all the elements in A, clear $$A$$ and visit $$T$$ in-order. For each node $$(x, m)$$ of $$T$$, append $$m$$ copies of $$x$$ to $$A$$. Correctness is trivial, and to prove the complexity bound it is sufficient to observe that at any given time the size of $$T$$ is $$O(\log n)$$.

• I don't have any idea about Red-Black Trees. – user35837 Dec 27 '16 at 18:52
• You may use any kind of height-balanced search tree instead. Have you heard about AVL trees? 2-3 trees? B/B+/B* trees? – quicksort Dec 27 '16 at 18:55
• what is the space complexity of your algorithm? Is it O (log n) ? – user35837 Jan 24 '17 at 10:59
• @Shivd Yes. We read the input but never modify it, therefore the space complexity equals the additional space, which is proportional to the size of the tree. – quicksort Jan 24 '17 at 11:22
• This answer describes, in fact, an algorithm that sorts $n$ integers in time-complexity $O(n\log k)$ and working-space-complexity $O(k)$, where $k$ is the number of distinct elements, $k\gt1$. – John L. Jun 25 '19 at 12:07

You don't do any sorting at all. Instead, you make one pass through the array S, collecting all unique values into a sorted array U, and for each unique value create a linked list of the indices of all items with that value.

Since U has a size O (log n), you can lookup any value in time O (log log n) using binary search. You do that n times, so O (n log log n) operations. Modifying array U is O (log^2 n) at most. Then creating the sorted array is O (n). Total O (n log log n).

If the number of unique values f (n) is larger you'll need something more clever than a simple sorted array (f (n) ≥ $$O ((n log n)^{1/2})$$ to do the job in O (n log f (n)).

• How do you get from $O(log² n)$ for inserting in the sorted array to Total $O(n\ log\ log\ n)$? – greybeard Dec 28 '16 at 7:58
• O(log^2 n) is muck less than O(n). – gnasher729 Dec 28 '16 at 16:29
• I still think there is an n missing in You do [lookup] n times, so O (log log n) operations. – greybeard Dec 28 '16 at 18:36
• What about space complexity ? Is it $O(\log n)$ ? – user35837 Jan 18 '17 at 15:00
• "Modifying array U is O (log^2 n) at most" -- how do you insert into the middle of an array in sublinear time? (Clearly, arrays are worst than balanced BSTs here.) – Raphael Jan 24 '17 at 18:44