# TADM2E 4.23

## Problem

4-23. We 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.

## Solution

With a self-balancing binary search tree, we can achieve O(*log k*) search and insertion (where *k* is the number of elements in the tree).

1. For each element in the sequence *S*, try and insert it into the tree.

- If the element is present, we increment a *count* variable stored at a node.

- If the element is not present, we insert the node and set the *count* = 1.

2. Traverse the tree in order and add elements according to the *count*.

Since the tree is guaranteed not to exceed *log n* elements, search and insertion take O(*log log n*).

Thus, this entire algorithm takes O(*n * log log n* + *log n*) = O(*n * log log n*) as required.