Re: stable algorithm with complexity O(n)

[pruebauno]

> 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.
--
http://mail.python.org/mailman/listinfo/python-list