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.

Answer 2

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.

Answer 3

You can always sort by sorting a parallel collection of indices or pointers or whatever. This works for both lists and vectors.

The reason sorting a list is slower is the fastest sorting algorithms require random access, i.e. the ability to be able to fetch immediately the value at a given index. You don't get that with lists. To get the 10th item in a linked list (say) you have to start at the beginning and move forward 10 times.