The original post links to this page: http://calmerthanyouare.org/2013/05/31/qsort-shootout.html http://calmerthanyouare.org/2013/05/31/qsort-shootout.html The

The original post links to this page: http://calmerthanyouare.org/2013/05/31/qsort-shootout.html http://calmerthanyouare.org/2013/05/31/qsort-shootout.html There is an explanation provided that may be the reason, but it is not entirely convincing. Smoothsort is a variation of heapsort that performs especially well on nearly sorted inputs. It’s a pretty complicated beast and it does take some effort to wrap one’s head around it. Keith Schwarz has posted a nice walkthrough that the interested reader should check out. Considering that musl libc puts simplicity among its design goals, the choice of smoothsort could seem odd. The code is however clean and readable and getting an O(nlogn)O(nlog⁡n) worst case with near linear complexity for nearly sorted inputs is a pretty sweet deal.