data structures sorting

if we have n elements with keys:{0,1,-1} and we开发者_开发知识库 want to sort them,how many comparison at least we have in the worst case?

Here is a solution that runs in O(n):

1. Create an array of three lists.

2. For each key/value entry, do

   lists[entry.key + 1].append(entry)
   

3. Concatenate the three lists into one long list.

This way you have no comparisons between keys.

With a small fixed number of possible values, you can sort in linear time with something like counting sort.

It depends on the algorithm used and distribution of the of elements.