Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Smoothsort
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, smoothsort is a <a href="/facts/Comparison_sort/X1PvE50c">comparison-based</a> <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorting algorithm</a>. A variant of <a href="/facts/Heapsort/Cz22lLKq">heapsort</a>, it was invented and published by <a href="/facts/Edsger_Dijkstra/910x0MjT">Edsger Dijkstra</a> in 1981. Like heapsort, smoothsort is an <a href="/facts/In-place_algorithm/Ghe2PJUF">in-place algorithm</a> with an upper bound of <i><a href="/facts/Big_O_notation/weFFjSWg">O</a></i>(<i>n</i> log <i>n</i>) operations (see <a href="/facts/Big_O_notation/weFFjSWg">big O notation</a>), but it is not a <a href="/facts/Stable_sort/PwHpj1Gs">stable sort</a>.[<i>self-published source?</i>] The advantage of smoothsort is that it comes closer to <i>O</i>(<i>n</i>) time if the <a href="/facts/Adaptive_sort/8BPWrNSD">input is already sorted to some degree</a>, whereas heapsort averages <i>O</i>(<i>n</i> log <i>n</i>) regardless of the initial sorted state. </p>