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
Credited To
Source Smoothsort (Wikipedia)
In Field
Source Smoothsort (Wikipedia)
Invented By
Source Smoothsort (Wikipedia)
Uses Design Technique
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
Invented By: Edsger W. Dijkstra, Lead section
invented and published by Edsger Dijkstra in 1981
In Field: Algorithms and Complexity Theory, Lead sentence
smoothsort is a comparison-based sorting algorithm.
In Group: Comparison Sorting Algorithms, Lead section
comparison-based sorting algorithm
Credited To: Edsger W. Dijkstra, Lead
A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981.
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.