comp.lang.c++

In article , asdfsf@asd.com says...
> How long does it take to sort elements in a std::list in worst case?

The standard doesn't give a worst case for this operation.

> I have read that quicksort on average (depends on partitioning) takes
> O(nlgn). But is quicksort used when sorting a std::list?

The standard doesn't say. It appears to have been written with the idea
of allowing either Quicksort or merge-sorting as the implementation. In
theory, it could probably be implemented in other ways (e.g. a heap
sort) but I'd guess most implementations use one of those two.

> And is it possible to sort faster than O(nlgn) in general - not looking
> a best case?

Not if you sort based on comparisons of the items being sorted. There
are things like bucket sorts, but the circumstances in which they can be
applied are fairly restricted.

--
Later,
Jerry.

The universe is a figment of its own imagination.