I implemented my own shellsort, shown in plot below are the timings for it.

0 means std::sort, used for comparision

1 means single thread

2 to 12 means multi-thread (pthreads)

enter image description here

Which algorithm is used by STL sort?



closed as off-topic by Evil, David Richerby, Discrete lizard, Yuval Filmus, vonbrand Aug 1 '18 at 13:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – David Richerby, Discrete lizard, Yuval Filmus, vonbrand
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ There are multiple implementations of STL. Some of them are available online: cplusplus.com/forum/general/219746. $\endgroup$ – Yuval Filmus Jul 12 '18 at 16:39
  • 2
    $\begingroup$ At any rate, this seems beyond the scope of this site. $\endgroup$ – Yuval Filmus Jul 12 '18 at 16:39

The C++ Library Specification does not prescribe any particular algorithm or implementation strategy. Every implementor is free to choose any algorithm, strategy, or combination of algorithms and strategies they please.

An implementor targeting resource-constrained IoT sensor devices, for example, may choose a different algorithm than one who targets high-performance workstations or servers.

Note that the C++ Library Specification does prescribe certain complexity guarantees that an implementor must obey:

$O(N \log N)$ comparisons, where $N = \texttt{last - first}$.

This may restrict the choice of algorithms. For example, Quicksort cannot be used in this case.

  • $\begingroup$ It's more correct to say that quicksort alone cannot be used in this case. All real-world industrial-strength sort systems tend to use a combination of "basic" sort algorithms and may dynamically adjust their behaviour as the key distribution becomes more clear. The obvious example is quicksort falling back to insertion sort for the base case. $\endgroup$ – Pseudonym Jul 13 '18 at 5:05

ShellSort is bad choice due to inefficient use of CPU caches.

You question answered in https://stackoverflow.com/questions/5038895/does-stdsort-implement-quicksort


Not the answer you're looking for? Browse other questions tagged or ask your own question.