c++ vector sorting

Question

This is a generic question about the mechanism behind sorting using the STL std::sort function. I've read some posts about sorting and that, in general, sorting vectors is faster than sorting linked lists. Is this true for vectors and linked lists of structures/objects? For a linked list of structures, I feel sorting can easily be achieved by just modifying the indexes. On the other hand, sorting for vectors seems like it would involve physically switching the data locations of the data of the structure/object since they are contiguous (is this true?). In that case it seems sorting linked lists would be faster.

EDIT!!!: Now with picture:

So I guess the question is better phrased: Which is faster for sorting objects, sorting a linked list OR a vector (although this might depend on the size of the object)? Also, is the sorting for a linked list done as shown in 3) and is the sorting done for a vector done as showing in 2)?

Answer 1

Sorting of list is specialized (i.e. list has function sort and cannot be sorted with std::sort).

void sort();
template <class Compare> void sort(Compare comp);

Complexity: Approximately N log(N) comparisons, where N == size().

std::sort in generalized.

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

Complexity: O(N log(N)) (where N == last - first) comparisons.

Note that result of std::list::sort is same as std::stable_sort. Note that there are no information in standard, how sort should be realized. It's implementation-defined.