Which Sorting Algorithm Is Used by Stl's List::Sort()

Which sorting algorithm is used by STL's list::sort()?

The standard doesn't require a particular algorithm, only that it must be stable, and that it complete the sort using approximately N lg N comparisons. That allows, for example, a merge-sort or a linked-list version of a quick sort (contrary to popular belief, quick sort isn't necessarily unstable, even though the most common implementation for arrays is).

With that proviso, the short answer is that in most current standard libraries, std::sort is implemented as a intro-sort (introspective sort), which is basically a Quicksort that keeps track of its recursion depth, and will switch to a Heapsort (usually slower but guaranteed O(n log n) complexity) if the Quicksort is using too deep of recursion. Introsort was invented relatively recently though (late 1990's). Older standard libraries typically used a Quicksort instead.

stable_sort exists because for sorting array-like containers, most of the fastest sorting algorithms are unstable, so the standard includes both std::sort (fast but not necessarily stable) and std::stable_sort (stable but often somewhat slower).

Both of those, however, normally expect random-access iterators, and will work poorly (if at all) with something like a linked list. To get decent performance for linked lists, the standard includes list::sort. For a linked list, however, there's not really any such trade-off -- it's pretty easy to implement a merge-sort that's both stable and (about) as fast as anything else. As such, they just required one sort member function that's required to be stable.

which sorting algorithm is used for std::list's sort member function?

It's implementation defined. However, it must follow these restrictions (§23.2.​2.4):

Stable: the relative order of the equivalent elements is preserved.

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

So it's a stable sort with O(nlog n).

Which sorting algorithm is used in stl and .net base library default search?

.NET uses a variation of Quicksort (Sedgewick's median of 3 Quicksort).

Unless you are an expert in sorting, I would be surprised if you can beat the built-in Sort over a wide range of data (including random, already ordered and reverse ordered sets). Resorting to unsafe code is usually a bad idea...

Which sorting algorithm is used by Microsoft's STL::list::sort()?

Just so you don't have to rely on second hand information, the the sort code is right in the list header - it's about 35 lines.

Appears to be a modified iterative (non-recursive) merge sort with up to 25 bins (I don't know if there's a particular name for this variant of merge sort).

Which type of sorting is used in the std::sort()?

Most implementations of std::sort use quicksort, (or usually a hybrid algorithm like introsort, which combines quicksort, heapsort and insertion sort).

The only thing the standard requires is that std::sort somehow sort the data according to the specified ordering with a complexity of approximately O(N log(N)); it is not guaranteed to be stable. Technically, introsort better meets the complexity requirement than quicksort, because quicksort has quadratic worst-case time.

What algorithms are used in C++11 std::sort in different STL implementations?

Browsing the online sources for libstdc++ and libc++, one can see that both libraries use the full gamut of the well-known sorting algorithms from an intro-sort main loop:

For std::sort, there is a helper routine for insertion_sort (an O(N^2) algorithm but with a good scaling constant to make it competitive for small sequences), plus some special casing for sub-sequences of 0, 1, 2, and 3 elements.

For std::partial_sort, both libraries use a version of heap_sort (O(N log N) in general), because that method has a nice invariant that it keeps a sorted subsequence (it typically has a larger scaling constant to make it more expensive for full sorting).

For std::nth_element, there is a helper routine for selection_sort (again an O(N^2) algorithm with a good sclaing constant to make it competitive for small sequences). For regular sorting insertion_sort usually dominates selection_sort, but for nth_element the invariant of having the smallest elements perfectly matches the behavior of selection_sort.

std::list sort algorithm runtime

If every element is within k positions of its proper place, then insertion sort will take less than kN comparisons and swaps/moves. It's also very easy to implement.

Compare this to the N*log(N) operations required by merge sort or quick sort to see if that will work better for you.

Sort list using STL sort function

The standard algorithm std::sort requires random access iterators, which std::list<>::iterators are not (list iterators are bidirectional iterators).

You should use the std::list<>::sort member function.

---

Related Topics