Editing Smoothsort (section)

{{Short description|Comparison-based sorting algorithm}}
{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=[[File:Smoothsort.gif||alt=An animation depicting smoothsort's operation, showing the heap being built and then disassembled,]]
|caption=Smoothsort operating on an array which is mostly in order.  The bars across the top show the tree structure.
|data=[[Array data structure|Array]]
|time={{math|''O''(''n'' log ''n'')}}
|best-time={{math|''O''(''n'')}}
|average-time={{math|''O''(''n'' log ''n'')}}
|space={{math|''O''(''n'')}} total, {{math|''O''(1)}} auxiliary
|optimal=When the data is already sorted
}}

In [[computer science]], '''smoothsort''' is a [[comparison sort|comparison-based]] [[sorting algorithm]]. A variant of [[heapsort]], it was invented and published by [[Edsger Dijkstra]] in 1981.<ref name=EWD-796a>{{Cite EWD|796a|16 Aug 1981|Smoothsort – an alternative to sorting in situ|quote=One can also raise the question why I have not chosen as available stretch lengths: ... 63 31 15 7 3 1 which seems attractive since each stretch can then be viewed as the postorder traversal of a balanced binary tree. In addition, the recurrence relation would be simpler.  But I know why I chose the Leonardo numbers:}}</ref> Like heapsort, smoothsort is an [[in-place algorithm]] with an upper bound of {{math|''[[Big O notation|O]]''(''n'' log&nbsp;''n'')}} operations (see [[big O notation]]),{{r|hertel}} but it is not a [[stable sort]].<ref>{{cite web
 |title=Fastest In-Place Stable Sort
 |first=Craig |last=Brown
 |date=21 Jan 2013
 |url=http://www.codeproject.com/Articles/26048/Fastest-In-Place-Stable-Sort
 |publisher=[[Code Project]]
}}{{self-published source|date=January 2016}}</ref>{{self-published inline|date=January 2016}}<ref>{{cite web
 |title=Where is the smoothsort algorithm used?
 |first=David |last=Eisenstat
 |date=13 September 2020
 |website=Stack Overflow
 |url=https://stackoverflow.com/questions/63872296/where-is-the-smoothsort-algorithm-used/63872426#63872426
 |access-date=2020-10-28
 |quote=Smoothsort is not stable, and stability is often more desirable than in-place in practice
}}</ref>  The advantage of smoothsort is that it comes closer to {{math|''O''(''n'')}} time if the [[Adaptive sort|input is already sorted to some degree]], whereas heapsort averages {{math|''O''(''n'' log&nbsp;''n'')}} regardless of the initial sorted state.