How do different languages ​​sort in their standard libraries?

Question

From what I read (briefly), Java and Python look like they use timsort in their standard libraries, whereas the sorting method in C stdlib is called qsort because it was quicksort once.

What algorithm do standard languages ​​currently use in their standard libraries and why did they choose this algorithm? Also, did C deviate from quicksort?

I know that on this issue there is a lack of “urgent problems that I am facing” and may seem open to some, but knowing how / why certain algorithms are chosen as standard seems quite useful, but relatively inexperienced. I also feel that in the depths of the answer regarding problems that depend on the language (data types?) And specific machines (cache hits?), One could better understand how different languages ​​and algorithms work than unify them.

Answer 1

C does not specify the algorithm qsort will use.

In the current glibc (2.17) qsort , memory is allocated (using malloc or alloca if the required memory is really small) and uses a merge sort algorithm. If the memory requirements are too high or if malloc does not work, it uses a quick sort algorithm.

Answer 2

In musl we use Smooth Sort . Conceptually, this is a variant of the sort heap (and similarly in-place time and O (n log n)), but it has the nice property that the worst performance approaches O (n) for already sorted or almost sorted input . I'm not sure if this is the best choice, but it is very difficult to do better with the local worst case O (n log n) algorithm.

Being a little-known invention of Dijkstra, he also makes it cool. :-)

Answer 3

My CC library provides qsort , heapsort and mergesort speaking on the page:

The qsort() and qsort_r() functions are CAR implementations of the Chorus "quick sort" algorithm, an option for sorting partitions; in particular, see DE Knut Q Algorithm. Quicksort takes an average time of O (n lg n). This implementation uses median selection to avoid the worst O (n ² ) behavior.

The heapsort() function is a JWJ implementation of William "heapsort" Algorithm, a sorting option for selection; in particular, see DE Knuth N. Heapsort Algorithm takes O (n lg n) worst-case time. Its only advantage over qsort() is that it uses almost no additional memory; and qsort() does not allocate memory, this is implemented using recursion.

The mergesort() function requires additional memory of size nel * width ; it should be used only if the space is not standing at a height. The mergesort() function is optimized for data with an existing order; its worst time is O (n lg n); its best case is O (n).

Usually qsort() faster than mergesort() , which is faster than heapsort() . The availability of memory and the pre-existing order in the data may make this incorrect.

There are many open source C libraries that you can look at if you want to see specific implementation details.

How much “why system X chose algorithm Y” is a rather complicated question to answer significant questions - if you are not lucky to find a rationale in the documentation, you should ask designers directly.

Answer 4

I quickly scanned qsort () in the C11 standard, and I could not find any information on how qsort() should be implemented and the expected complexity of the time / space of the algorithm. All he has to say is about some conditions regarding the comparator function.

What this means is that an implementation can choose any algorithm based on a comparator that is suitable for qsort (). For example, an implementation may use a naive algorithm, such as a bubble type, to implement qsort (), which is not an effective quick sort . The bottom line is that before implementing the solution using the actual algorithm.