Lower-bound on comparison-based sorting of n values in the range 1 to k

Question

Can we do better than O(n lg n) running time for a comparison-based algorithm when all of the values are in the range 1 to k, where k < n.

Counting sort and radix sort are not comparison-based algorithms and are disallowed. By a decision tree analysis, it seems like there are k^n possible permutations. There are 2^h leaves, so it should be possible to solve the problem in O(n lg k) time with a comparison-based sorting algorithm.

Please do not give a non-comparison based sorting algorithm for solving this problem, all sorting must be based on comparisons between two elements. Thanks!

Answer 1

It may easily be done in the bound you specified. Build a binary tree of k leaves and include a count value on each leaf. Processing each element (adding it or bumping the count) will be O(lg k) if one uses a suitable balancing algorithm, so doing all of them will be O(n lg k). Reconstituting the list will then be O(n).

Answer 2

Ok, if you insist you want comparisons.

You have k elements. So, keep a tree structure that will hold all the elements.

Go over the list of items, each time add the item to the tree. If the item is already in the tree, just increment the counter in that node. (or if you want the actual items you can keep a list in each node)

The tree will have no more than k items.

in the end, go over the tree in an inorder way, and add the items back in the right order (while adding the amount that are in the node's counter).

Complexity: O(nlogk)