# Sort elements in a std::list?

Discussion in 'C++' started by desktop, Apr 7, 2008.

1. ### desktopGuest

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, Apr 7, 2008

2. ### Juha NieminenGuest

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
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

Juha Nieminen, Apr 7, 2008

3. ### Jerry CoffinGuest

In article <ftdr82\$fnl\$-c.dk>, 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.

Jerry Coffin, Apr 7, 2008
4. ### Juha NieminenGuest

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.

Juha Nieminen, Apr 8, 2008
5. ### Ivan VecerinaGuest

"Jerry Coffin" <> wrote in message
news:...
: In article <ftdr82\$fnl\$-c.dk>, 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.

Note that the standard specifies that std::list::sort results in a
*stable* sort: that is, the relative order of equivalent elements is not
changes.
This basically excludes Quicksort as an implementation.

The standard also does not mention the existence of a "worst case" for
std::list::stort, nor the need for allocating memory or copying objects.
While these omissions are not explicit statements, they would make it
difficult to use any algorithm other than Mergesort.

It would be very surprising and difficult for a standard library
implementation to choose any algorithm different from Mergesort (or some
derivative of it). All the (major) existing lib implementations use a
form of Mergesort.

Regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Brainbench MVP for C++ <> http://www.brainbench.com

Ivan Vecerina, Apr 8, 2008
6. ### Pascal J. BourguignonGuest

"Ivan Vecerina" <> writes:

> "Jerry Coffin" <> wrote in message
> news:...
> : In article <ftdr82\$fnl\$-c.dk>, 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.
>
> Note that the standard specifies that std::list::sort results in a
> *stable* sort: that is, the relative order of equivalent elements is not
> changes.
> This basically excludes Quicksort as an implementation.

Not at all. You can easily use a wrapped lessp, that uses the

bool wrapped_lessp(T* a,T* b){
return(lessp(a,b)
or ((not lessp(b,a))
and (a<b)));}

Then no two elements are equal (by wrapped_lessp), but equal elements
(by lessp) are still sorted together, keeping their original order.

If the elements are not pointers, then you can spend O(n) to wrap them
in 'pointers', that is, to sort a vector of indices instead, using:

bool wrapped_lessp(int a,int b){
return(lessp(v[a],v)
or ((not lessp(v,v[a]))
and (a<b)));}

Anyways, sorting big lists (more than 3 elements) will be done more
efficiently by going thru a vector.

--
__Pascal Bourguignon__

Pascal J. Bourguignon, Apr 8, 2008
7. ### Jerry CoffinGuest

In article <2ddc4\$47fb8e06\$55da1598\$>,
says...

[ ... ]

> Note that the standard specifies that std::list::sort results in a
> *stable* sort: that is, the relative order of equivalent elements is not
> changes.
> This basically excludes Quicksort as an implementation.

Actually, no it doesn't. It's quite trivial for a quick sort on a linked
list to be stable.

The usual implementation of quicksort for arrays works by doing two more
or less separate scans, one from the bottom up and the other from the
top down. When each finds an element that's out of order compared to the
chosen pivot, you swap those two elements. This means you need only
minimal extra storage to partition the array (basically, room for one
extra element during swapping, plus two positions in the array).

For linked lists, partitioning is actually simpler: you choose a pivot,
and then create two linked lists, one of elements that compare less than
the pivot, and the other of elements greater than or equal to the pivot.
Since you can move elements around just by manipulating the pointers,
the only auxiliary storage you need is a position into the linked list,

> The standard also does not mention the existence of a "worst case" for
> std::list::stort, nor the need for allocating memory or copying objects.
> While these omissions are not explicit statements, they would make it
> difficult to use any algorithm other than Mergesort.

As you may be able to guess from the discussion above, nearly the ONLY
requirement that would really distinguish between the two would be one
on worst case performance. Quick sort still have O(N*N) worst case,
where merge sort is always O(N lg N). Worse, since you don't get random
access to the elements, you can't really use a median of three or
anything like that to choose your pivot element; you typically just use
the first element in the list as the pivot (at least for the first
partition), making the worst case a bit more common.

OTOH, once you know the size of a partition, you can swap the element
from the middle of the list to the beginning. Since std::list is doubly
you can do a median of three pivot selection on subsequent partitions.
IOW, while a linked list tends to hurt the performance of quick sort,
with a little care you can minimize that effect.

> It would be very surprising and difficult for a standard library
> implementation to choose any algorithm different from Mergesort (or some
> derivative of it). All the (major) existing lib implementations use a
> form of Mergesort.

It certainly would NOT be difficult to use quick sort. Just to give one
example, I'm quite sure that P.J. Plaugar would have absolutely NO
difficulty at all with implementing list::sort as a quick sort.

The only real question is whether he _would_. For linked lists, quick
sort provides little or no advantage over a merge sort, but at least in
theory its worst case is much worse. As such, I suppose seeing it would
be surprising but (at least to me) only mildly so.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jerry Coffin, Apr 9, 2008
8. ### Jerry CoffinGuest

In article <>,
says...

[ ... ]

> Not at all. You can easily use a wrapped lessp, that uses the
> 'address' of the elements. If the elements are already pointers, then:
>
> bool wrapped_lessp(T* a,T* b){
> return(lessp(a,b)
> or ((not lessp(b,a))
> and (a<b)));}

As I pointed out elsethread, this is really completely unnecessary. In
any case, I don't see how it could work correctly -- the addresses of
elements in a linked list have no relationship at all to their current
relative positions in the list.

> Anyways, sorting big lists (more than 3 elements) will be done more
> efficiently by going thru a vector.

The speed difference probably doesn't justify the extra work until you
get quite a bit larger than 3 elements, but yes, for very many elements
a vector will generally be faster. Then again, I'll openly admit that
I'm somewhat biased -- I've pointed out before that I think linked lists
are heavily overused, and _rarely_ a good choice for much of anything.
I'd just as soon not get back into that particular discussion at the
moment though...

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jerry Coffin, Apr 9, 2008
9. ### Kai-Uwe BuxGuest

Jerry Coffin wrote:

> In article <>,
> says...

[snip]
>> Anyways, sorting big lists (more than 3 elements) will be done more
>> efficiently by going thru a vector.

>
> The speed difference probably doesn't justify the extra work until you
> get quite a bit larger than 3 elements, but yes, for very many elements
> a vector will generally be faster.

[snip]

I don't think the size of the sequence will matter all that much, but I
conjecture that in a speed contest list vs vector on sorting, a list will
win if swapping the objects is very expensive compared to rearranging some
pointers. The main reason that quick-sort wins against heap-sort is that
quick-sort does not move data around so often.

Best

Kai-Uwe Bux

Kai-Uwe Bux, Apr 9, 2008
10. ### James KanzeGuest

On Apr 9, 6:53 am, Jerry Coffin <> wrote:
> In article <>,
> says...

> [ ... ]
> > Anyways, sorting big lists (more than 3 elements) will be done more
> > efficiently by going thru a vector.

> The speed difference probably doesn't justify the extra work
> until you get quite a bit larger than 3 elements, but yes, for
> very many elements a vector will generally be faster.

Doesn't this depend on the type of the elements? Swapping
elements in a list is just pointer manipulations; swapping them
in a vector means actually moving the elements themselves. If
the elements are expensive to copy, and don't support an
optimized swap, that could make a significant difference.

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

James Kanze, Apr 9, 2008
11. ### Jerry CoffinGuest

In article <8f828965-ee43-4f83-891e-d950ae26c1e7@

[ ... sorting list being slower than sorting vector ]

> Doesn't this depend on the type of the elements? Swapping
> elements in a list is just pointer manipulations; swapping them
> in a vector means actually moving the elements themselves. If
> the elements are expensive to copy, and don't support an
> optimized swap, that could make a significant difference.

Yes, that's why I said "generally" -- things stored in a standard
container should generally be fairly cheap to copy. That's _less_ of an
issue with std::list than std::vector (for one example) but your object
is still copied into the collection, so if it's really expensive to
copy, you probably want to wrap it in something (e.g. a smart pointer)
to make copying cheap.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jerry Coffin, Apr 10, 2008