Algorithm for sorting multisets

Question

Hi

I'm looking for an algorithm (preferably in C/C++/Java or similar) to sort a multiset. By scouting the internet I've come to the conclusion that I should be able to do it in O(n log h) time. With h being the number of distinct elements and n the total number of elements. I wasn't however able to find an algorithm that utilizes the fact that a multiset may contain repeated elements to sort faster.

Best Regards!

Answer 1

Use a balanced binary tree.

During insertion, if you try to insert an already existing element, instead of inserting, update a count in the node.

At the end, do an in-order traversal. The count tells you how many times a node is repeated.