TY  - RPRT
T1  - Smoothsort's behavior on presorted sequences
T3  - Saarbrücken, 1982
A1  - Hertel,Stefan
Y1  - 2011/08/01
N2  - In [5], Mehlhorn presented an algorithm for sorting nearly sorted sequences of length n in time 0(n(1+log(F/n))) where F is the number of initial inversions. More recently, Dijkstra[3] presented a new algorithm for sorting in situ. Without giving much evidence of it, he claims that his algorithm works well on nearly sorted sequences. In this note we show that smoothsort compares unfavorably to Mehlhorn's algorithm. We present a sequence of length n with O(nlogn) inversions which forces smoothsort to use time Omega(nlog n), contrasting to the time O(nloglogn) Mehlhorn's algorithm would need.
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/4062
ER  -