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

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

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

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

"Approximately NlogN comparisons", according to the Standard.

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

Maybe. Maybe not. It isn't specified.

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

I doubt it, but take a look at D. Knuth, "TAOCP", volume 3.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

desktop wrote:
> How long does it take to sort elements in a std::list in worst case?
>
> I have read that quicksort on average (depends on partitioning) takes
> O(nlgn). But is quicksort used when sorting a std::list?
>
> And is it possible to sort faster than O(nlgn) in general - not looking
> a best case?

I have to wonder why you put the elements in a list (rather than, say, a
map) if you're going to sort them. Then they could be sorted on-the-fly
as they go in...

Also, you don't *have* to use std::sort.

Andy

Andy Champ wrote:
> desktop wrote:
>> How long does it take to sort elements in a std::list in worst case?
>>
>> I have read that quicksort on average (depends on partitioning) takes
>> O(nlgn). But is quicksort used when sorting a std::list?
>>
>> And is it possible to sort faster than O(nlgn) in general - not
>> looking a best case?
>
> I have to wonder why you put the elements in a list (rather than,
> say, a map) if you're going to sort them. Then they could be sorted
> on-the-fly as they go in...

The speed of adding to a map has no comparison with that of a list.

> Also, you don't *have* to use std::sort.

Actually, you can think of a map as using std::sort _every time_
you insert something, plus rebalancing. The price is there, you
just never think you're paying it until you profile the insertions.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

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

In article <ftdr82$fnl$1@news.net.uni-c.dk>, 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.

Victor Bazarov wrote:
> Andy Champ wrote:
>
> The speed of adding to a map has no comparison with that of a list.

True - but it's the only cost.

>
>> Also, you don't *have* to use std::sort.
>
> Actually, you can think of a map as using std::sort _every time_
> you insert something, plus rebalancing. The price is there, you
> just never think you're paying it until you profile the insertions.
>

Now there I think you have me. I tend not to play with large sorts, and
haven't had one big enough to profile in *years*, so I'll have to assume
you know what you're talking about. On previous history you probably do.

One minor question though - isn't map more like an insertion sort?

Andy

Andy Champ wrote:
> I have to wonder why you put the elements in a list (rather than, say, a
> map) if you're going to sort them. Then they could be sorted on-the-fly
> as they go in...

A list takes slightly less memory than a set and some operations are
way faster (such as push_back). Also traversing the list is probably
faster than traversing a set.

If you are going to add tons of elements to the data container and
then sort it, the memory saving of using the list may be worth it.