Editing Smoothsort (section)

==Analysis==
Smoothsort takes {{math|''O''(''n'')}} time to process a presorted array, {{math|''O''(''n'' log&nbsp; ''n'')}} in the worst case, and achieves nearly linear performance on many nearly sorted inputs.  However, it does not handle all nearly sorted sequences optimally.  Using the count of inversions as a measure of un-sortedness (the number of pairs of indices {{mvar|i}} and {{mvar|j}} with {{math|''i'' < ''j''}} and {{math|''A''[''i''] > ''A''[''j'']}}; for randomly sorted input this is approximately {{math|''n''<sup>2</sup>/4}}), there are possible input sequences with {{math|''O''(''n'' log&nbsp;''n'')}} inversions which cause it to take {{math|Ω(''n'' log&nbsp;''n'')}} time, whereas other [[adaptive sort|adaptive sorting]] algorithms can solve these cases in {{math|''O''(''n'' log&nbsp;log&nbsp;''n'')}} time.<ref name="hertel">{{cite journal
 |last=Hertel |first=Stefan
 |title=Smoothsort's behavior on presorted sequences
 |journal=[[Information Processing Letters]]
 |volume=16 |issue=4 |date=13 May 1983 |pages=165–170
 |url=http://scidok.sulb.uni-saarland.de/volltexte/2011/4062/pdf/fb14_1982_11.pdf |archive-url=https://web.archive.org/web/20151208051150/http://scidok.sulb.uni-saarland.de/volltexte/2011/4062/pdf/fb14_1982_11.pdf |archive-date=2015-12-08 |url-status=live
 |doi=10.1016/0020-0190(83)90116-3
}}</ref>

The smoothsort algorithm needs to be able to hold in memory the sizes of all of the trees in the Leonardo heap.  Since they are sorted by order and all orders are distinct, this is usually done using a [[bit vector]] indicating which orders are present.  Moreover, since the largest order is at most {{math|''O''(log&nbsp;''n'')}}, these bits can be encoded in {{math|''O''(1)}} machine words, assuming a [[transdichotomous machine model]].

Note that {{math|''O''(1)}} machine words is not the same thing as ''one'' machine word.  A 32-bit vector would only suffice for sizes less than {{math|1=''L''(32) = 7049155}}.  A 64-bit vector will do for sizes less than {{math|1=''L''(64) = 34335360355129 ≈ 2<sup>45</sup>}}.  In general, it takes {{math|1/log<sub>2</sub>(''[[Golden ratio|φ]]'') ≈ 1.44}} bits of vector per bit of size.