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

You're correct, a sort of std::vector is going to be slow if copying an element is slow. C++11 introduces move semantics which might help, elements can be moved instead of copied.

A linked list is quite easy to sort with a merge sort, which is O(n log n) the same as any other good sorting algorithm. The difference is in the overhead.

As always benchmarking your particular case is a good idea if the results are important to you.