Editing Smoothsort (section)

==Poplar sort==
A simpler algorithm inspired by smoothsort is '''poplar sort'''.<ref>{{cite journal
 |title=Smoothsort revisited
 |first1=Coenraad |last1=Bron |author-link1=Coenraad Bron
 |first2=Wim H. |last2=Hesselink
 |journal=Information Processing Letters
 |volume=39 |issue=5 |pages=269&ndash;276 |date=13 September 1991
 |doi=10.1016/0020-0190(91)90027-F
}}</ref>  Named after the rows of trees of decreasing size often seen in Dutch [[polder]]s, it performs fewer comparisons than smoothsort for inputs that are not mostly sorted, but cannot achieve linear time for sorted inputs.

The significant change made by poplar sort in that the roots of the various trees are ''not'' kept in sorted order; there are no "stepson" links tying them together into a single heap.  Instead, each time the heap is shrunk in the second phase, the roots are searched to find the maximum entry.

Because there are {{mvar|n}} shrinking steps, each of which must search {{math|''O''(log&nbsp;''n'')}} tree roots for the maximum, the best-case run time for poplar sort is  {{math|''O''(''n'' log&nbsp;''n'')}}.

The authors also suggest using perfect binary trees rather than Leonardo trees to provide further simplification, but this is a less significant change.

The same structure has been proposed as a general-purpose [[priority queue]] under the name '''post-order heap''',<ref>{{cite conference
 |title=The Post-Order Heap
 |first1=Nicholas J. A. |last1=Harvey  |first2=Kevin |last2=Zatloukal
 |url=https://people.csail.mit.edu/nickh/Publications/PostOrderHeap/FUN_abstract.html
 |conference=Third International Conference on Fun with Algorithms (FUN 2004)
 |location=[[Elba]], Italy |date=26–28 May 2004
}}</ref> achieving {{math|''O''(1)}} [[Amortized analysis|amortized]] insertion time in a structure simpler than an implicit [[binomial heap]].