How do different languages implement sorting in their standard libraries? [closed]

Question

From what I have (briefly) read, Java and Python both look like they make use of timsort in their standard libaries, while the sorting method in C's stdlib is called qsort because it once was quicksort.

What algorithm do typical languages have implemented in their standard libraries today, and why did they choose that algorithm? Also, did C deviate from quicksort?

I know this question lacks an "actual problem(s) that [I] face" and may seem open ended to some, but knowing how/why certain algorithms are chosen as standard seems pretty useful but relatively untaught. I also feel as though an in depth answer addressing concerns that are language specific (data types?) and machine specific (cache hits?) would provide more insight to how different languages and algorithms work than uni cares to explain.

Answer 1

In musl, we use Smooth Sort. Conceptually it's a variant of heap sort (and likewise in-place and O(n log n) time), but it has the nice property that the worst-case performance approaches O(n) for already-sorted or near-sorted input. I'm not convinced it's the best possible choice, but it appears very difficult to do better with an in-place algorithm with O(n log n) worst-case.

Being a little-known invention of Dijkstra's also makes it kind of cool. :-)

Answer 2

C does not specificy the algorithm to be used by qsort.

On current glibc (2.17) qsort allocates memory (using malloc or alloca if memory required is really small) and uses merge sort algorithm. If memory requirements are too high or if malloc fails it uses quicksort algorithm.