Where is the smoothsort algorithm used?

Admin 1
Viewed 266

While studying Algorithm in my University, I have come across this algorithm called Smoothsort. It is a great algorithm as it is an adaptive algorithm, the time complexity can vary from being a linear complexity to linearithmic, and it is an in-place algorithm as well. However, the resources on this algorithm is very scarce and those are available are quite hard to understand. However, the reason I am posting this question, is to learn about the use cases and when it should be used and when it should not be used?

That's all I wanted to know and thank you very much for answering or reviewing this question.

heapsort dijkstra heap sorting algorithm
1 Answers

musl libc uses Smoothsort to implement qsort(). This Stack Overflow answer from the library author describes the reasoning: it's worst-case O(n log n) (unlike Quicksort), in-place (unlike mergesort), and adaptive (unlike heapsort). I think Smoothsort doesn't get used so much for some combination of

  • Smoothsort is not stable, and stability is often more desirable than in-place in practice because it means that the sorting order in the presence of equal keys is completely determined. musl has the freedom allowed by the C standard not to be stable, and one of the design goals is not to allocate memory except as explicitly requested (this is why musl strstr() doesn't use KMP, for example).

    Note that there exist in-place, stable, O(n log n)-time sorting algorithms, but the constant factor is too big to be practical.

  • Adaptivity is more of a nice to have, and Smoothsort is more complicated than heapsort.

  • Smoothsort isn't widely known due to its omission from almost all undergraduate algorithms courses (and even graduate courses – I didn't see it in school, for example).

user_21446690
Related