stable algorithm with complexity O(n)

pruebauno at latinmail.com pruebauno at latinmail.com
Mon Dec 15 17:07:50 CET 2008


On Dec 15, 11:05 am, prueba... at latinmail.com wrote:
> > Non-comparison sorts are a useful technique, but it's changing the
> > problem, and they are only useful in very limited circumstances. There's
> > a good reason that most sort routines are based on O(n*log n) comparison
> > sorts instead of O(n) bucket sorts or radix sorts.
>
> This is an assumption that I never quite understood. What most people
> want is to have sorted data, they don't care if I used a sorting or
> non-sorting comparison to do it. I think it is just that in most cases
> n is not very big anyway and comparison sorts make it easier on the
> programmer to create arbitrary types that are sortable.

I meant they don't care if I use a comparison or non-comparison sort
of course.



More information about the Python-list mailing list