comp.lang.c++

desktop wrote:
> How long does it take to sort elements in a std::list in worst case?

The C++ standard probably doesn't specify, and I haven't actually
checked what compilers use in practice, but I'm pretty sure most
compilers use merge sort.

Merge sort is especially suited for doubly-linked lists because such
lists can be merge-sorted in-place (ie. only changing prev/next
pointers), without the need for any additional memory. Merge sort can be
implemented in such way that it doesn't require random access, and thus
it can be applied to a list. Given that the worst-case of merge sort is
O(n*log n), it makes it very efficient regardless of what the list contains.

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

In theory quicksort could be applied to a list (like merge sort, it's
possible to implement quicksort in a way that doesn't require random
access). However, given that the worst-case of quicksort is O(n^2) I
think most implementations prefer using merge sort, which is very fast
and in the case of doubly-linked lists doesn't require any additional
memory (unlike with arrays).

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

It has been mathematically proved that a sorting algorithm which
is based on comparison between the elements cannot be faster than
O(n log n). Faster sorting algorithms exist, but they cannot used if
only comparison between elements is available (they usually only work
with things like integers). See for example
http://en.wikipedia.org/wiki/Radix_sort