Smoothsort: Difference between revisions

Revision as of 20:57, 25 November 2018

Revision as of 00:27, 4 June 2019

Line 11:

}}

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 [[Big O notation|O]](''n'' log&nbsp;''n''),{{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]]}}</ref>{{self-published inline|date=January 2016}} The advantage of smoothsort is that it comes closer to O(''n'') time if the [[Adaptive sort|input is already sorted to some degree]], whereas heapsort averages O(''n'' log&nbsp;''n'') regardless of the initial sorted state.

==Overview==

Line 71:

==External links==

* [http://www.enterag.ch/hartwig/order/smoothsort.pdf Commented transcription of EWD796a, 16-Aug-1981]

{{Edsger Dijkstra}}