Smoothsort is a comparison-based sorting algorithm and a variant of heapsort, invented and published by Edsger Dijkstra in 1981. Like heapsort it is an in-place algorithm with a worst-case running time of O(n log n) and is not a stable sort. Its advantage over heapsort is that it approaches O(n) time as the input becomes more nearly sorted, whereas heapsort takes O(n log n) time on average regardless of how sorted the input already is.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Classification
Design Technique Connections
In Field
Source Smoothsort (Wikipedia)
Uses Design Technique
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
Sources
1. Smoothsort (Wikipedia)
- Wikipedia Smoothsort infobox time O(n log n)
- Smoothsort: stretch-size decomposition "can be found in a greedy manner"
Wikipedia infobox: time complexity linearithmic
linearithmic
In Field: Algorithms and Complexity Theory, Lead sentence
smoothsort is a comparison-based sorting algorithm.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.