std::list::sort _is_a_ merge-sort for libstdc++. Why are you seeing different running times?

[dhruvbird]

Is the mergesort you compared a different implementation compared to that used by std::list?

[Morwenn]

@dhruvbird Yes: std::list::sort is allowed and encouraged to relink nodes while a general sorting algorithm knows nothing about the data structure and isn't allowed to relink nodes. The mergesort I compared against works the same with lists, vectors or any data structure supporting at least bidirectional iterators. Basically, the mergesort I checked against only moves or swaps values; it cannot play with nodes. The list-specific mergesort also tends to be a bit more memory-efficient.

IIRC, I probably compared against this naive mergesort implementation which falls back on an insertion sort for when the size of the sub-collection to sort is small.

Oh yeah, before I forget about it: std::list::sort might appear to be somewhat slower for some inputs, but it's probably because I benchmarked the sorting algorithms against a collection of integers. Relinking list nodes becomes great when the objects get bigger and more expensive to move around. I expect std::list::sort to beat the other algorithms for bigger data types.

[dhruvbird]

Basically, the mergesort I checked against only moves or swaps values; it cannot play with nodes.

Ah! That explains it!

Oh yeah, before I forget about it: std::list::sort might appear to be somewhat slower for some inputs, but it's probably because I benchmark the sorting algorithms against a collection of integers. Nodes relinking becomes great when the objects get bigger and more expensive to move around. I expect std::list::sort to beat the other algorithms for bigger data types.

That makes sense, since you'd be relinking 4?? pointers per swap v/s one element swap.