[ ... ]
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,
and a pointer to the head of the second 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
linked, you then have access to the first, middle and last elements, so
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.
