How do different languages implement sorting in their standard libraries?
c, programming-languages, sorting, standard-library
Solution
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. :-)
Problem
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.