Content deleted Content added
m →Operations: Oops |
→Analysis: make a link |
||
Line 61:
==Analysis==
Smoothsort takes {{math|''O''(''n'')}} time to process a presorted array and {{math|''O''(''n'' log ''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 ''n'')}} inversions which cause it to take {{math|Ω(''n'' log ''n'')}} time, whereas other [[adaptive sort|adaptive sorting]] algorithms can solve these cases in {{math|''O''(''n'' log log ''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 |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 ''n'')}}, these bits can be encoded in {{math|''O''(1)}} machine words, assuming a [[transdichotomous machine model]].
| |||