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:

enter image description here

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

You could always allocate the memory on the heap and use a vector of pointers. — GWW, Sep 14 '12 at 21:11
A related (but I don't think duplicate) question may shed some light on this. [...difference between list.sort and std::sort](http://stackoverflow.com/questions/8017215/whats-the-difference-between-list-sort-and-stdsort) — Mark Wilkins, Sep 14 '12 at 21:18
@Mark: Thanks for the thread, especially this part of the answer: "Moreover, the member functions can take advantage of the special nature of the list data structure by simply relinking the list nodes, while the standard algorithm has to perform something like swap (or something to that effect), which requires object construction, assignment and deletion." I think I'll probably have to benchmark to get a more direct answer but I'm thinking sorting the linked list will be faster. — JustinBlaber, Sep 14 '12 at 21:42

ForEveR · Answer 1 · 2012-09-14T21:24:58.950

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.

score 2 · Answer 2 · answered Sep 14 '12 at 21:16

2

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.

answered Sep 14 '12 at 21:16

john

85,011
4
57
81

Merge sort is a fast algorithm, and it doesn't require random access. – Mark Ransom Sep 14 '12 at 21:27
True but merge sort requires O(N) auxiliary space. If you allow that then you might as well create a vector of pointers and sort that. Then you have no need to copy elements. – john Sep 14 '12 at 21:33
No, merge sort doesn't take auxiliary space on a linked list - you remove elements from the input list and put them in the output list. – Mark Ransom Sep 14 '12 at 21:37
Hmm, I'm surprised I didn't know this. – john Sep 14 '12 at 21:43

score 2 · Accepted Answer · answered Sep 14 '12 at 21:26

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.

c++ vector sorting

3 Answers3